both the Quran and various Islamic traditions which refer to the presence of true believers both before and during Muhammad’s alleged "call" to prophethood. The Quran mentions that Adam, Noah, the Patriarchs, the twelve tribes of Israel, Moses, Jesus etc., were all believers and many of them even messengers who lived a long time before Muhammad:
Behold, thy Lord said to the angels: "I will create a vicegerent on earth." They said: "Wilt Thou place therein one who will make mischief therein and shed blood?- whilst we do celebrate Thy praises and glorify Thy holy (name)?" He said: "I know what ye know not."… And behold, We said to the angels: "Bow down to Adam" and they bowed down. Not so Iblis: he refused and was haughty: He was of those who reject Faith. We said: "O Adam! dwell thou and thy wife in the Garden; and eat of the bountiful things therein as (where and when) ye will; but approach not this tree, or ye run into harm and transgression."… When learnt Adam from his Lord words of inspiration, and his Lord Turned towards him; for He is Oft-Returning, Most Merciful. S. 2:30, 34-35, 37
We have sent thee inspiration, as We sent it to Noah and the Messengers after him: we sent inspiration to Abraham, Isma'il, Isaac, Jacob and the Tribes, to Jesus, Job, Jonah, Aaron, and Solomon, and to David We gave the Psalms. S. 4:163
We gave him Isaac and Jacob: all (three) guided: and before him, We guided Noah, and among his progeny, David, Solomon, Job, Joseph, Moses, and Aaron: thus do We reward those who do good: S. 6:84
And when Ibrahim and Ismail raised the foundations of the House: Our Lord! accept from us; surely Thou art the Hearing, the Knowing: Our Lord! and make us both submissive (muslimayni) to Thee and (raise) from our offspring a nation submitting (ommatan muslimatan) to Thee, and show us our ways of devotion and turn to us (mercifully), surely Thou art the Oft-returning (to mercy), the Merciful. Our Lord! and raise up in them an Apostle from among them who shall recite to them Thy communications and teach them the Book and the wisdom, and purify them; surely Thou art the Mighty, the Wise. And who forsakes the religion of Ibrahim but he who makes himself a fool, and most certainly We chose him in this world, and in the hereafter he is most surely among the righteous. When his Lord said to him, Be a Muslim (aslim), he said: I submit myself (aslamtu) to the Lord of the worlds. And the same did Ibrahim enjoin on his sons and (so did) Yaqoub. O my sons! surely Allah has chosen for you (this) faith, therefore die not unless you are Muslims (illa waantum muslimoona). Nay! were you witnesses when death visited Yaqoub, when he said to his sons: What will you serve after me? They said: We will serve your God and the God of your fathers, Ibrahim and Ismail and Ishaq, one God only, and to Him do we submit (wanahnu lahu muslimoona). S. 2:127-133 Shakir
When Jesus found Unbelief on their part He said: "Who will be My helpers to (the work of) Allah?" Said the disciples: "We are Allah's helpers: We believe in Allah, and do thou bear witness that we are Muslims. S. 3:52
Ibrahim was not a Jew nor a Christian but he was (an) upright (man), a Muslim (musliman), and he was not one of the polytheists. S. 3:67 Shakir
They are not all alike; of the followers of the Book there is an upright party; they recite Allah's communications in the nighttime and they adore (Him). They believe in Allah and the last day, and they enjoin what is right and forbid the wrong and they strive with one another in hastening to good deeds, and those are among the good. And whatever good they do, they shall not be denied it, and Allah knows those who guard (against evil). S. 3:113-115 Shakir
Then will Allah say: "O Jesus the son of Mary! Recount My favour to thee and to thy mother. Behold! I strengthened thee with the holy spirit, so that thou didst speak to the people in childhood and in maturity. Behold! I taught thee the Book and Wisdom, the Law and the Gospel and behold! thou makest out of clay, as it were, the figure of a bird, by My leave, and thou breathest into it and it becometh a bird by My leave, and thou healest those born blind, and the lepers, by My leave. And behold! thou bringest forth the dead by My leave. And behold! I did restrain the Children of Israel from (violence to) thee when thou didst show them the clear Signs, and the unbelievers among them said: ‘This is nothing but evident magic.’ And behold! I inspired the disciples to have faith in Me and Mine Messenger: they said, 'We have faith, and do thou bear witness that we bow to Allah as Muslims.’" S. 5:110-111
Lo! it is from Solomon, and lo! it is: In the name of Allah, the Beneficent, the Merciful; Exalt not yourselves against me, but come unto me as those who surrender (muslimeena). ... So, when she came, it was said (unto her): Is thy throne like this? She said: (It is) as though it were the very one. And (Solomon said): We were given the knowledge before her and we had surrendered (wakunna muslimeena) (to Allah). ... It was said unto her: Enter the hall. And when she saw it she deemed it a pool and bared her legs. (Solomon) said: Lo! it is a hall, made smooth, of glass. She said: My Lord! Lo! I have wronged myself, and I surrender (aslamtu) with Solomon unto Allah, the Lord of the Worlds. S. 27:30-31, 42, 44 Pickthall