There are many synagogues known to have existed in the Second Temple period both from literature and archaeology (see lists on Hebrew and English Wikipedia). So the question isn't whether they existed, but more what purpose they served. This subject is addressed in Ezra Fleischer's article "On the Beginnings of Obligatory Jewish Prayer" (in Hebrew), specifically pp. 402-414.
To summarize his argument, synagogues weren't used for public prayer during the Second Temple period. בית כנסת (like its Greek counterpart sunagogē) means "house of gathering," not "house of prayer." What took place in synagogues is adduced from contemporary sources, which never mention public prayer in a synagogue. In fact, the structure of synagogues that have been discovered seems to indicate places for sitting on all four sides of the building (whereas a house of prayer would more likely have all seats facing the Temple or the ark).
On the other hand, contemporary sources do mention it as a place for gathering and reading from the Torah. To mention a few of them: An inscription on one Israeli synagogue says that Theodotus "built this synagogue for reading the Torah and learning the commandments." Philo (Life of Moses 2.215-216) describes the houses of prayer of his own day (in Alexandria) as "schools of wisdom." The gospels and the Acts of the Apostles portray Israeli and diaspora synagogues as a place in which the Torah was read and where Jesus and Paul tried to teach. Reading from the Torah in the synagogue has survived until this day as part of the public prayer, but in those days it wasn't part of public prayer, it was the main purpose of the gathering in the synagogue, while prayer was individual.
The reason why synagogues became places for public prayer is because public prayer was standardized after the destruction of the Second Temple by Rabban Gamli'el. The standard prayer seems to have been composed at this time, along with the practice to say prayers communally. Due to the need to pray with ten people, prayers became part of the synagogue.