Prophets came to the world to teach the worship of one and only one God. Prophets came to all communities. And ever since first Human Adam (As), Islam is there. The problem where with hypocrites who added up and reduced from the religion. The prophet right before Muhammed (saw) was Jesus (As), where we Muslims and Christians both agree him as the Messiah, Christ, Virgin birth, re coming etc. In the bible where the words of Jesus are recorded, no where does he say worship him or he's the God incarnated or taught Trinity. Instead in many many places he quoted God is only One, worship only Him (These are just a very few to help you find some, Google it to read yourself; Mark 12:29, John 17:3, John 5:44, Luke 18:19) . Still Christian missionaries who preached later invented and innovated Trinity. Still, even for today, anyone who put their observance in reading bible, the words of Jesus (As), they can see the truth in worshiping One and only one God. Quran in multiple places states that there were many among the people of books who are believers. There's a case stated where some Christians came to visit prophet Muhammad SAW and accept him where they say they were already a believer before.
In the case of other religions like Hinduism, there's also monotheism prescribed in their Vedas, there are in many places this is written; here are few
"Ekam evadvitiyam"
"He is One only without a second."
[Chandogya Upanishad 6:2:1]1
"Na casya kascij janita na cadhipah."
"Of Him there are neither parents nor lord."
[Svetasvatara Upanishad 6:9]2
"Na tasya pratima asti"
"There is no likeness of Him."
[Svetasvatara Upanishad 4:19]3
The following verses from the Upanishad allude to the inability of man to imagine God in a particular form:
"Na samdrse tisthati rupam asya, na caksusa pasyati kas canainam."
"His form is not to be seen; no one sees Him with the eye."
[Svetasvatara Upanishad 4:20]4
There were the case where God cursed some people to be monkeys when they missed prayer and disobeyed. Their descendants might be the some isolated tribes living without touch to outer world. There are some tribes where they worship One and only one God.