From the time of the exodus out of Egypt, a great mixed multitude went up with the Hebrew people, bringing their flocks and cattle with them, a mixture of nations of proselytes (see: Where did the converts camp in the desert?).
How would Gentiles come to faith and be accepted as believing Jews? Are there any references in the Torah to inform us?
The Gibeonites, later called nethinim, eventually converted. The Tanach also tells us of Uriah the Hittite, a very observant Jew from ethnic Hittite stock, whose ancestors evidently converted.
HaShem burdens adopted Noachides like נַעֲמָן Naaman with שָׁלוֹם peace (not halakhot)[Gittin 57b:6],[Sanhedrin 74b:10].
Regarding converts [Sanhedrin 96b.8], examples include: נְבוּזַרְאֲדָן Nebuzaradan (who taught HaShem’s desires to Babylonian soldiers [Eikhah Rabbah 5.11]), along with Shemaya & Avtalyon (discussed in [Gittin 57b.7]) who became Torah scholars.
“The Gemara adds that some of Haman’s descendants studied Torah in Bnei Brak, and some of Sisera’s descendants taught children Torah in Jerusalem, and some of Sennacherib’s descendants taught Torah in public. Who are they? They are Shemaya and Avtalyon, the teachers of Hillel the Elder.”
Rav Soloveitchik explains the conversion process of a gentile (Kol Dodi Dofek, Conversion by Circumcision and Immersion 2):
A gentile who wishes to join the nation must take upon himself both covenants. He places himself in the ambit of Jewish fate and sanctifies himself for the acceptance of the Jewish destiny. The act of conversion involves associating oneself as a member of the people of the Covenants of Egypt and of Sinai. Keep this important principle in mind: there is no such thing as partial conversion. One cannot omit one iota of either of these two Covenants. Total devotion to the Jewish people — as a nation that God took to Himself in Egypt, with all its tribulations, suffering, responsibilities, and actions; and as a holy people that is itself consecrated, heart and soul, to the God of Israel and His halakhic and moral demands — is the absolute foundation of Judaism and hence is also the basis of conversion. (emphasis mine).
Rav Soloveitchik thus explains that associating oneself as a member of the people of the Covenants of Egypt and of Sinai is a way to connect oneself to the Jewish people.
According to the Or HaChaim on Leviticus 19:34, these converts where people whose soul were already attached to that of those from the Jewish people.
[...] This is why the Torah describes them as "like one of your very own," i.e. you have much more in common with converts than you think. [...] The only reason these proselytes are embraced wholeheartedly by the Torah is that the Torah views these converts as people who are returning to their roots.
So, according to this opinion, the converts were not really that "strangers", they were already somehow attached to the Jewish people, and found out of their spiritual connection to them.
There are also sources that discuss the fact that after Yisro went to visit Moshe Rabbeinu in the desert, he went home to convert his people. Rashi, in his commentary to Shemos 18:5 explains that Yisro came to the desert "to hear the words of Torah". So, according to this, it would seem logical (did not have seen any sources for this though), that Yisro spoke these words of Torah, he just learned, to his people in Midian, to where he returned. It would seem logical that there were people that would feel an connection after hearing these words of Torah, and wanted to convert. (see here).
