The town of "Bethlehem" appears over 40 times in 12 books of the Old Testament:

Bethlehem is first mentioned in conjunction with the death of the matriarch Rachel.

So Rachel died and was buried on the way to Ephrath (that is, Bethlehem). (Gen 35:19)

Now as for me, when I came from Paddan, Rachel died, to my sorrow, in the land of Canaan on the journey, when there was still some distance to go to Ephrath; and I buried her there on the way to Ephrath (that is, Bethlehem)." (Gen 48:7)

Ruth and Boaz met at Bethlehem, married and bore their son Obed, the father of Jesse who in turn was the father of King David.

So Naomi returned, and with her Ruth the Moabitess, her daughter-in-law, who returned from the land of Moab. And they came to Bethlehem at the beginning of barley harvest. (Ruth 1:22)

The Bethlehem Bulla

God sends the prophet Samuel to Bethlehem to find the new king.

Now the LORD said to Samuel, "How long will you grieve over Saul, since I have rejected him from being king over Israel? Fill your horn with oil and go; I will send you to Jesse the Bethlehemite, for I have selected a king for Myself among his sons." (1 Sam 16:1)

Bethlehem is the hometown of King David. While fighting the Philistines, who had a garrison in Bethlehem, a thirsty David wishes out loud for some water.

David had a craving and said, "Oh that someone would give me water to drink from the well of Bethlehem which is by the gate!" (2 Sam 23:15)

Micah prophesies God's promised ruler over Israel (Messiah) will be born in Bethlehem.

Now muster yourselves in troops, daughter of troops; They have laid siege against us; With a rod they will smite the judge of Israel on the cheek. But as for you, Bethlehem Ephrathah, Too little to be among the clans of Judah, From you One will go forth for Me to be ruler in Israel. His goings forth are from long ago, From the days of eternity." (Mic 5:1-3)

But apart from the Bible, there hasn't been any archeological evidence of Bethlehem of the Old Testament found until recently.

On May 23, 2012, the Israel Antiquities Authority announced the discovery of a clay seal bearing the name "Bethlehem" in ancient Hebrew script. Measuring only 1.5 cm (0.59 inches) long, the small bullae was unearthed just outside Jerusalem's Old City.

The seal was written in ancient Hebrew script from the First Temple Period, and pottery found nearby also dated back to the same time. This placed the bullae during the first Jewish Temple period, between the eighth and seventh century B.C., at a time when Jewish kings reigned over the ancient kingdom of Judah and 700 years before Jesus was born.

It is believed that the bulla was used to seal tax shipments of silver or agricultural produce exported from Bethlehem to the King of Judah, either Hezekiah, Manasseh or Josiah, in Jerusalem.

The inscription on this small piece of clay was:

Bishv'at: in the seventh

Bat Lechem: Bethlehem"

[Lemel]ekh: king

Shmuel Achituy, an expert in ancient scripts at Israel's Ben-Gurion University said that the discovery is the oldest reference to Bethlehem ever found outside of the Bible. There are only some 40 other existing seals of this kind from the First Temple Period making this a significant find, both because such seals are rare, and because this is the first to mention Bethlehem.

The ancient seal provides evidence that Bethlehem existed at least 700 years before Jesus and was indeed a city in the kingdom of Judah.