As discussed before, in the beginning of Paul’s ministry he gained eager converts from Gentiles who were in the synagogue. These individuals were known as God-fearers, those who were attracted to Judaism but had not converted fully. This was highly fertile ground for fledgling Christianity. Contrary to modern Judaism, ancient Judaism seems to have attracted many converts and potential converts from the Gentile population.

Pagan histories of the time record the disdain that was felt because of Jewish proselytization (whither it was active or passive proselytization). Cassius Dio records:

They have also another name that has been acquired,–i.e., the country has been called Judaea, and the people themselves Jews. I do not know from what source this title was first given them, but it applies also to all the rest of mankind, although of foreign race, who cherish their customs.

It was well known to Cassius that people could convert to Judaism. It was a big enough phenomena he specifically mentions the occurrence. Later on he writes:

As there had been a large influx of Jews into Rome and they were converting many of the native inhabitants to their principles he expelled the great majority of them.

This was the expulsion in 19 AD (under Tiberius), not to be confused with the expulsion in 49 AD (under Claudius). In reference to the 49 AD event (some argue that Cassius is saying no expulsion happened), Cassius writes:

In the matter of the Jews, who had again increased so greatly that by reason of their multitude it would have been hard without raising a tumult to bar them from the City, he decided not to drive them out, but ordered them to follow that mode of life prescribed by their ancestral custom and not to assemble in numbers.

Both these passages from Claudius indicate a large Jewish conversion. Judaism was a metropolitan religion, appealing to many Gentiles. The Jews, in that day, welcomed all comers who could follow their customs, and the Jews would integrate those individuals into their community. The Jews had such great influence that even Rome conformed its laws to match Jewish law instead of vice versa. Augustine records Seneca in City of God:

When he was speaking concerning those Jews, he said, When, meanwhile, the customs of that most accursed nation have gained such strength that they have been now received in all lands, the conquered have given laws to the conquerors.

The Bible records the same picture. Luke, throughout Acts, gives us glancing references to this phenomenon:

Act 10:1 There was a certain man in Caesarea called Cornelius, a centurion of the band called the Italian band,
Act 10:2 A devout man, and one that feared God with all his house, which gave much alms to the people, and prayed to God alway.

The first Gentile to be grafted into Jewish communion without kosher food laws or circumcision was a God-fearing Centurion. This is also interesting because the Romans exempted the Jews from military service, as the Jews practiced no work on the Sabbath. This was mind boggling to Peter.

Later, after the conversion of Paul, the reader again meets God-fearing Gentiles:

Act 13:14 But when they departed from Perga, they came to Antioch in Pisidia, and went into the synagogue on the sabbath day, and sat down.
…
Act 13:16 Then Paul stood up, and beckoning with his hand said, Men of Israel, and ye that fear God, give audience.

Israel and those that fear God are two separate groups. This is made clear when after Paul stops speaking. The Jews exit the synagogue and the Gentiles ask Paul to preach more:

Act 13:42 And when the Jews were gone out of the synagogue, the Gentiles besought that these words might be preached to them the next sabbath.
…
Act 13:44 And the next sabbath day came almost the whole city together to hear the word of God.
Act 13:45 But when the Jews saw the multitudes, they were filled with envy, and spake against those things which were spoken by Paul, contradicting and blaspheming.

Notice that the Jews become envious. Perhaps they were used to being the main draw for converts and now an upstart preaching a new gospel gains a bigger audience then they ever could. The Jews proceed to drive him out just after Paul explains his mission to the Gentiles.

In Iconium, the reader again meets more God-fearing Gentiles:

Act 14:1 And it came to pass in Iconium, that they went both together into the synagogue of the Jews, and so spake, that a great multitude both of the Jews and also of the Greeks believed.

Paul’s primary teaching point is the synagogue. Sometimes he preaches elsewhere, when he is driven out of the synagogue or there is no synagogue. But the Gentiles primarily hear his preaching inside the synagogue.

The next God fearer that is listed in Acts is another individual, Lydia. Lydia might not be her real name but instead a name derived from the place she was from. In any case, she seems to be a Gentile in a city without a synagogue (Philippi). Lydia had worshiped God before Paul. But because of Paul “her heart was opened”:

Act 16:14 And a certain woman named Lydia, a seller of purple, of the city of Thyatira, which worshipped God, heard us: whose heart the Lord opened, that she attended unto the things which were spoken of Paul.

In Thessalonica Paul again enters a synagogue and converts Gentiles:

Act 17:1 Now when they had passed through Amphipolis and Apollonia, they came to Thessalonica, where was a synagogue of the Jews:
…
Act 17:4 And some of them believed, and consorted with Paul and Silas; and of the devout Greeks a great multitude, and of the chief women not a few.

In Athens, Luke seems to specify three groups of people: Jews in the synagogue, Gentiles in the synagogue and random people in the market. Notice the location change as only applied to the third category:

Act 17:17 Therefore disputed he in the synagogue with the Jews, and with the devout persons, and in the market daily with them that met with him.

Paul then goes to Corinth and again preaches to Gentiles in the synagogue:

Act 18:4 And he reasoned in the synagogue every sabbath, and persuaded the Jews and the Greeks.

After he is rejected (this is directly after preaching to the Jews and Greeks), he walks next door to a God-fearing Gentile:

Act 18:5 And when Silas and Timotheus were come from Macedonia, Paul was pressed in the spirit, and testified to the Jews that Jesus was Christ.
Act 18:6 And when they opposed themselves, and blasphemed, he shook his raiment, and said unto them, Your blood be upon your own heads; I am clean: from henceforth I will go unto the Gentiles.
Act 18:7 And he departed thence, and entered into a certain man’s house, named Justus, one that worshipped God, whose house joined hard to the synagogue.

Most of the references to God-fearing Gentiles throughout the Bible are indirect references. It was well known to the original readers of the New Testament that there was a God-fearer movement, so much so that it is addressed only in passing. Luke did not need to explain to his reader what God-fearers were, everyone was already familiar with them.

In summary, early Judaism had already gained a large following from the Gentiles by the time Paul showed up on the scene, with both converts and God-fearers. The pagan historians described this massive conversion, and there is ample evidence in Acts of this fact. Paul leveraged this receptive audience to his advantage. The God-fearers is where most of Paul’s success was found. This gives the context to Paul’s statement in Romans:

Rom 9:6 Not as though the word of God hath taken none effect. For they are not all Israel, which are of Israel:

They are not all Israel which are of Israel, many of them were once Gentiles.