There is no way to know exactly how early Tu B'Av began. The first mention of this date is in the Mishnah (compiled and edited in the end of the second century), where Rabban Shimon ben Gamliel is quoted saying, "There were no better (i.e. happier) days for the people of Israel than the Fifteenth of Av and Yom Kippur, since on these days the daughters of Israel/Jerusalem go out dressed in white and dance in the vineyards. What were they saying: Young man, consider whom you choose (to be your wife)?"(Ta'anit, Chapter 4).
The Gemara (the later, interpretive layer of the Talmud) attempts to find the origin of this date as a special joyous day, and offers several explanations. One of them is that on this day the Biblical "tribes of Israel were permitted to mingle with each other," namely: to marry women from other tribes (Talmud, Ta'anit 30b). This explanation is somewhat surprising, since nowhere in the Bible is there a prohibition on "intermarriage" among the 12 tribes of Israel. This Talmudic source probably is alluding to a story in the book of Judges (chapter 21): After a civil war between the tribe of Benjamin and other Israelite tribes, the tribes vowed not to intermarry with men of the tribe of Benjamin.