Túathal was the son of a former High King deposed by an uprising of "subject peoples" who returned at the head of an army to reclaim his father's throne. The oldest source for Túathal's story, a 9th-century poem by Mael Mura of Othain, says that his father, Fíacha Finnolach, was overthrown by the four provincial kings, Elim mac Conrach of Ulster, Sanb (son of Cet mac Mágach) of Connacht, Foirbre of Munster and Eochaid Ainchenn of Leinster, and that it was Elim who took the High Kingship. During his rule Ireland suffered famine as God punished this rejection of legitimate kingship. Túathal, aided by the brothers Fiacha Cassán and Findmall and their 600 men, marched on Tara and defeated Elim in battle at the hill of Achall. He then won battles against the Ligmuini, the Gailióin, the Fir Bolg, the Fir Domnann, the Ulaid, the Muma, the Fir Ól nÉcmacht and the Érainn, and assembled the Irish nobility at Tara to make them swear allegiance to him and his descendants.
Later versions of the story suppress the involvement of the provincial nobility in the revolt, making the "subject peoples" the peasants of Ireland. The Lebor Gabála Érenn adds the detail of Túathal's exile. His mother, Eithne Imgel, daughter of the king of Alba (originally meaning Britain, later Scotland), was pregnant when Fíachu was overthrown, and fled to her homeland where she gave birth to Túathal. Twenty years later Túathal and his mother returned to Ireland, joined up with Fiacha Cassán and Findmall, and marched on Tara to take the kingship.
The Annals of the Four Masters features a similar revolt a few generations earlier, led by Cairbre Cinnchait, against the High King Crimthann Nia Náir. On this occasion Crimthann's son Feradach Finnfechtnach is the future king who escaped in his mother's womb, although the Annals claim he returned to reclaim his throne only five years later. The story repeats itself a few generations later with Elim's revolt against Fíachu, and the exile and return of Túathal. Geoffrey Keating harmonises the two revolts into one. He has Crimthann hand the throne directly to his son, Feradach, and makes Cairbre Cinnchait, whose ancestry he traces to the Fir Bolg, the leader of the revolt that overthrew Fíachu, killing him at a feast. The pregnant Eithne flees as in the other sources. Cairbre rules for five years, dies of plague and is succeeded by Elim. After Elim had ruled for twenty years, the 20- or 25-year-old Túathal was prevailed upon to return. He landed with his forces at Inber Domnainn (Malahide Bay). Joining up with Fiacha Cassán and Findmall and their marauders, he marched on Tara where he was declared king. Elim gave battle at the hill of Achall near Tara, but was defeated and killed.
Túathal fought 25 battles against Ulster, 25 against Leinster, 25 against Connacht and 35 against Munster. The whole country subdued, he convened a conference at Tara, where he established laws and annexed territory from each of the four provinces to create the central province of Míde (Meath) around Tara as the High King's territory. He built four fortresses in Meath: Tlachtga, where the druids sacrificed on the eve of Samhain, on land taken from Munster; Uisneach, where the festival of Beltaine was celebrated, on land from Connacht; Tailtiu, where Lughnasadh was celebrated, on land from Ulster; and Tara, on land from Leinster.
He went on to make war on Leinster, burning the stronghold of Aillen (Knockaulin) and imposing the bórama, a heavy tribute of cattle, on the province. One story says this was because the king of Leinster, Eochaid Ainchenn, had married Túathal's daughter Dairine, but told Túathal she had died and so was given his other daughter, Fithir. When Fithir discovered Dairine was still alive she died of shame, and when Dairine saw Fithir dead she died of grief.