One of the things that always seemed to be implied by Version 1.0, but rarely explicitly supported, was that some clans branched directly from others, and rather recently. For example, the Hellsguard all but surely branch from the Sea Wolves and recently adapted to the volcanic Farreach. Highlanders seemed to be Midlanders that stayed in the harsh mountain regions after the Sixth Umbral Calamity's floods receded, becoming stronger and bulkier where the air in thin and life is hard (ignoring that when this happens IRL, people tend to get shorter, too). This was contradicted in ARR, though; it is said that Highlanders domesticated the common sheep during the Age of Endless Frost - over a thousand years before.
So let's stick to confirmed facts!
The Highlander tribes of Gyr Abania have long been a violent lot. This, and the influence of northern dialects a la the Roegadyn, gave rise to their present naming conventions (see sticky). Remnants of ancient spiritual traditions remain the form of wooden talismans (often woven into their underclothes) and tattoos (sacred as they are intimidating). The brute, tribal aesthetic can also be seen their food; simple (but impressive) dishes such as large aldgoat steaks, well-seared but never overcooked. There were also some mentions tooth-filing and eyebrow-shaving as means of seeming more intimidating in combat, though these have gone unmentioned for a while.
They arrived in Gyr Abania following the floods of the Sixth Umbral Calamity (following a comet that many believed to be a sign from Rhalgr), putting the Highlanders in a prime position for history to record them as the first peoples to re-enter Eorzea after the waters receded. (This also being why they're called high-landers; the builders of mountain strongholds.) For over a thousand years, these mountain tribes warred over what little arable land existed. It was Anshelm Cotter, a tactical genius, who finally united what tribes didn't scatter before his advance (1100).
Ala Mhigan history, if relevant to your highlander:
Thus united, Ala Mhigo was raised mainly by Highlanders. Seeing as it was right on the land bridge leading into Ilsabard, they made sure that Ala Mhigo was a mighty bastion capable of repelling foreign invasion. Their military might being one of the few things they could export led to Ala Mhigan sellsword companies springing up in nearly every city-state to be used in their conflicts against one another. Unfortunately, Ul'dah's trade empire (with many ships) considerably undermined their ability to charge tolls on traders coming through the secure land bridge (1190).
Hoping to claim fertile land by conquest, King Manfred attempted to conquest the Black Shroud (1468), almost crushing the Gridanian forces before being driven back by a fledgling alliance of Eorzean city-states rallied by Ishgard, knowing that should Gridania fall the Ala Mhigans would be at their gates (and the already had the Dragonsong War to contend with). This would come to be known as the Autumn War (1469).
In the austerity that came after the wars, dissatisfaction with the crown swelled. The Fists of Rhalgr - the monks - gained considerable political influence. To forestall the erosion of the monarchy, the Fists were declared the state religion and given great influence. For at time this enmeshing of religion and state indeed led to stability, but King Theodoric would try to sever their influence (1546). He would declare himself above Rhalgr, ordained by the Destroyer's master, Nymeia. But this was simple pretense; when they Fists of Rhalgr protested, he brutally crushed them; all in temple, be they priest or refugee, burned (1552).
Growing paranoid, Theodoric's rule became more and more tyrannic. The executions began with rival claimants to the throne and moved ever downwards towards even smallfolk of any noteworthy wealth. His fears were only confirmed when even the queen turned against him, a conspiracy betrayed by a single noble. The brutality spurred the people to action, overthrowing their leader in a "popular revolution" defied not even by the king's own guard, the Corpse Brigade.
Unfortunately for the people, the rising tensions and violence had been encouraged from the shadows; gentle manipulations by spies of the Garlean Empire loyal to Gaius van Baelsar. As soon as Theodoric had been slain, the Imperial army sprung their trap, taking the city without a great battle or siege. Any who did not surrender or join the Resistance fled.
You can learn the nitty-gritty about Autumn War, the Fists of Rhalgr, and the fall of Ala Mhigo from Erik at the Pugilists' Guild.
The fall of Ala Mhigo caused a massive flood of Highlander refugees into the Black Shroud and Thanalan; moreso the latter, as the Elementals can be rather picky about who is allowed to stay, and where. Version 1.0 lampshaded the lack of female Highlanders (this being why Yda and Minfilia look like Midlanders) by saying that many of the daughters of Ala Mhigo stayed behind to fight in the Resistance, being no less skilled at arms.
As has ever been the case, many make their way as sellswords (and now adventurers), but thanks to the recent and radical distribution caused by the fall of Ala Mhigo, you can find a few Highlanders doing just about anything, just about anywhere to get by.