This question originally appeared on Quora, the knowledge-sharing network where compelling questions are answered by people with unique insights. You can follow Quora on Twitter, Facebook, and Google Plus.
Answer by Stephen Tempest, qualified amateur historian:
During the reign of Clovis is the best answer. He didn't unite the Gauls—he conquered the Gauls at the head of his army of Franks.
During the final years of the Roman Empire, the Franks, a Germanic people, were invited by the local Roman governors to settle in the lowlands at the mouth of the River Rhine and serve as auxiliary soldiers to defend the region from their less civilised brethren. The Franks were not united but divided into several tribes—the Salian Franks and Ripuarian Franks were the main groups, but there were other smaller tribes.
The Franks were illiterate, so all the contemporary written information we have about them was set down by the Romans in Latin. Even their name is Latin: They were the Franci, and the lands where they lived were called Francia. It's assumed that their own name for themselves was similar in sound, but we don't actually know what it was. Some historians have put forward the word frankō, which means “spear” or “javelin” in Old German. Others suggest the word frakaz, which meant “brave.” And they suggest that the tribes called themselves in Old German either the “spear people” or the “brave people.”
Clovis became leader of the Salian Franks in the year 481, at the age of 15. His capital was the city of Tournai (Tornacum in Latin) in modern-day Belgium. To the west, a rump of the Roman Empire still under direct Roman administration clung to power north of the Loire: Its leader, Flavius Syagrius, possibly held the title magister militum per Gallias, though the historian Gregory of Tours, writing a century later, refers to him as “King of the Romans.” His capital was the city of Soissons (Noviodunum), 62 miles northeast of Paris.
Five years after taking the throne, in 486, Clovis challenged Syagrius to a battle, defeated him, and conquered his kingdom. Clovis now ruled most of northern France. He had an alliance with the Ripuarian Franks thanks to his marriage to one of their princesses. The two Frankish tribes cooperated in an alliance against the Thuringians, another Germanic nation, and conquered their lands on the east bank of the Rhine. Most of Clovis' life was spent waging wars on one opponent or another. Gradually, by alliance or conquest, the smaller Frankish tribes were forced to accept his rulership.
At some point—probably around the year 496—Clovis converted to Christianity. This was traditionally said to be at the prompting of his (second) wife, who was herself a Christian. However, it's also likely that Clovis found the religion politically advantageous in dealing with his new Christian subjects. The Franks ruled over the Gallo-Romans as a conquered people—they had their own separate law codes, and the subjects had to pay tax to their Germanic overlords—but Clovis seems to have made at least some effort to integrate and win their loyalty.
Late in his life, Clovis put together a grand alliance of his fellow Franks, the Burgundians, and even the (Byzantine) Roman Empire in order to attack the Visigoths who ruled southern France from their capital of Toulouse (Tolosa). The battle of Vouillé (near Tours) in 507 was one of the decisive turning points of European history. Clovis won a decisive victory and conquered all the Visigothic lands as far as the Pyrenees. For the first time a single king ruled an independent state that stretched from the English Channel to the Pyrenees and from the Bay of Biscay to the Rhine (and beyond). In about 508 Clovis made the strategically located city of Paris the capital of his new, united kingdom of Francia.
Francia, or the regnum Francorum (“kingdom of the Franks”), would not always be united. Frankish custom was to divide a kingdom between all the previous king's sons after his death, rather than keeping it intact and handing it on to just one of them. The term Francia should thus be understood as a geographical term, meaning the area where the people called themselves Franks and obeyed Frankish law, rather than necessarily being the name of a political entity. Still, it does seem that the Franks continued to think of themselves as a single nation even when they were divided into multiple states. It was just that the status “king of the Franks” was one that could be shared by several people.
Future kings would expand the power of the regnum Francorum to far greater extents, until under Charlemagne it covered large parts of Germany and Italy and northern Spain. That large empire would then fragment again. The dates 842 and 843 are significant because in 842, two of Charlemagne's grandsons formed an alliance to fight against their other brother. The oath they swore was written down in three languages: Latin, and the “romana lingua” and “teudisca lingua”—that is, the Romance language and Teutonic language. This marks the first time in history that it was officially acknowledged that the Gallo-Roman people of France spoke a new language of their own that had become different to Latin. Furthermore, the text of the Oath of Strasbourg is usually considered to be the first written document in French.
A year later in 843, the three brothers settled their differences (for a time) in the Treaty of Verdun, which partitioned Charlemagne's empire into three. While such partitions were nothing new, it did solidify the growing division into Eastern Francia, where people spoke German, and Western Francia, where they spoke French. Eventually—by around the 10th century—the people of East Francia stopped thinking of themselves as Franks and instead identified with the broader identity of Germans. (Or the even more broad identity of the Holy Roman Empire.) As a result, the people of West Francia gradually stopped bothering to distinguish their kingdom as West and started simply calling it Francia again. But there was no particular date when that happened—it was a gradual process.