You could imagine that with the advent of a new religion, any followers of the last religion would be required to convert to the new religion.
Which followers of which religion converted to Judaism, when Judaism came on the scene?
How did they know that they had to convert to Judaism?
Rashi, BeReishis 12:5 says that Avraham and Sarah converted people to Judaism. The religion that was around before that time was paganism, as is known.
Your question implies that when a new religion shows up everyone switches to it like it's the latest new technology.
That is NOT the case. Some people did convert (a notable example is Yitro AKA Jethro), plus some Egyptians (the erev rav) and Canaanites. But the vast majority of the world did not convert.
And on top of that, Judaism does not ask them to. A non-Jew does not need to convert in order to have a meaningful relationship with God.
In general when Judaism "came on the scene" as you call it, its members were all descendants of Abraham.
No such "switch" happened. According to the simplest understanding of Jewish history, Judaism started with one man, Avraham, who recognized the creator of the world. He came to this realization himself, independent of anyone else. G-d blessed him that his descendants would be numerous, and they were. Several hundred years later, his descendants stood at Mount Sinai and received the Torah from G-d.
Every Jew today is either a descendant of those people, descended from people who converted somewhere along the way, or are converts themselves. Judaism does not claim to "inherit" from any other religion as I understand Christianity and Islam claim to.
i'm only going to post this answer because i didn't see anyone else cover these topics.
Many people think that before Abraham, no one worshipped God. But this isn't true, because we have Melkhitzedek who was a priest of God. If there is a priest of God, then more than likely there is some sort of formalized religion, or at the very least, a tradition passed down regarding God. Not much is said about Melchitzedek, so we can only speculate. But it can deifnitely be said that Avraham was successful where Melchitzedek failed, since Melchitzedek didn't spread monotheism throughout the world or convert any followers (that we know of). We also have the example of Bilaam knowing about God and being a valid prophet, another sign that this "Jewish religion" wasn't unique to the Jews.
So even though most of the world had varying pagan religions, there were a few monotheistic strains around. These were probably remnants of oral traditions brought down by the descendants of Noah, and throughout time much of that knowledge was probably lost due to lack of writing and lack of reading ability. Once one of the oral tradition transmitters dies, the information can never be brought back.
So the answer to your question was no, there wasn't any systemized religion that needed to "upgrade to Judaism." Even when people say the other religions were "paganism," it wasn't like there was an official pagan religion that everyone belonged to. There were hundreds if not thousands of different gods, or even differing beliefs on the same gods. There were even ancestral gods that belonged to families/clans. But what is clear is that the Biblical text makes note that there were other monotheists around, but that they didn't take any action to spread it as a religion.
This is a tricky question because, while Avrohom and Sarah were definitely the first Jews, there are some senses in which the Jewish people did not formally construct itself until later, with the giving of the Torah. So, in response to the question of "what religion people converted from," there are two different points at which they could have "converted."
1) Avraham and Sarah converted to Jewish-style monotheism from the ancient Semitic polytheistic religion of Avraham's father. Although there had been monotheists before (such as Adam, Eve, and Noah), idol worship was de rigueur in the land during Avraham's time.
Avraham had personal revelations which drew him toward belief in a Single Gd--causing him to rebel against his father--and eventually into covenant with that G-d. He then became the patriarch of a family and leader of a large group of followers, all monotheistic.
Not all of his followers nor of his descendants are considered "Jewish" by us today; we retroactively consider "Jewish" those who planted seeds for what has become our modern tradition.
2) When Divine Revelation was given to Moses at Mount Sinai in 2448 (1313 B.C.E.), the Jewish people came to exist in its current sense as a formal, proactively-defined religious and ethnic group. The basic laws, rituals, principles, and organization of Judaism as they are understood today were communicated by G-d to Moses, and thence to the Jewish people, at that time. This body of knowledge is what we call the Torah; it is how "Judaism" has been defined ever since.
So, as far as "what [the people] were converting from"--at that time they were converting from a general tradition of holiness and righteousness within monotheism, begun by Avrohom and Sarah, to a formal and codified system for the service of G-d, begun by Moses. This formal and codified system includes laws and rites that are considered central to Judaism today, including Shabbat, kosher diet, prayer, and the rules for charity and treatment of others.
...
To complicate all this: Jews have a traditional belief that Abraham and Sarah (along with some people in earlier generations, including Adam and Eve) followed the laws of the Torah in their entirety from the very beginning. That is, Avraham, Sarah, etc., already lived according to the laws that were told to Moses and the Jewish people only many years later. This fairly subtle and mystically-oriented belief, and how it squares with the idea that Judaism formally conceived of itself in 2448, are explained here.
