The Vandals fearing attacks from the Huns invaded the Roman Empire searching for a new homeland. They traveled through modern-day France and Spain, being attacked and driven out along the way before crossing into North Africa, taking the Roman lands (including Carthage without a fight) and setting up their own Empire. They then went on to sack Rome.
This also applies to the various other Germanic tribes that traveled West into Roman and Celtic lands during and after The Migration Period, such as the Goths, Franks, Angles, Saxons and Normans.
Also there were the Slavic peoples who came during the Middle Ages.
Early modern
The Sforza dynasty was started by the leader of a band of Private Military Contractors that used his men to take over an Italian city-state. They decided on Milan; Sforza ended up hiring Leonardo da Vinci when the latter ended up being too prissy for the Medicis' tastes.
In an internal conflict, often both sides can invoke this trope. Thus during The American Revolution, both Patriots and Loyalists were fighting for their homes and country, and in the end the losing side had to emigrate to Canada. The situation for Republicans and Loyalists during the Troubles in Northern Ireland was also like this.
The Flight of the Wild Geese. After the wars of the 17th century Irish soldiers emigrated in their thousands to work as mercenaries for their fellow Catholics in Spain, France, and Austria, rather than live under the unbearable political and religious oppression at home. As late as 1792 the Kings of France maintained several Irish regiments and during The Napoleonic Wars an Irish Legion was part of the French Army, while the Spanish army also contained many Irishmen or Irish-descended Spaniards. Descendants of the Geese included Patrice de Mac-Mahon (Marshal of France and first president of the French Third Republic) and Bernardo O'Higgins (another general and one of the founders of independent Chile).
The armies of the French Republic included many partisans of the failed popular uprisings in the Republic of the United Provinces of the Netherlands ("Holland") and the Austrian Netherlands (the "Belgian Rebellion") of the 1780s. When the French started to win the war, they annexed, among other things, what is now Belgium and formed the new-style Batavian Republic from the former United Provinces. This was later transformed into a kingdom for Napoleon's brother Louis and in 1810 annexed by France.
On the Allied side, there was a number of regiments formed by and from emigrés, royalists who had left France during the Revolution. Lacking success in their endeavours, the remaining emigrés eventually were for the most part absorbed into the armies of various European states and later returned to France either after an amnesty was declared or after the fall of Napoleon.
The Polish Legions of the French Army were formed after the Polish state was divided between Austria, Prussia and Russia in 1795, and the page quote is from a song originally written for one of the Legions, which later became the anthem of Polish patriots and then the restored Polish state. Their aim of restoring their homeland, which came to a transitory fruition of a sort with the founding of the Duchy of Warsaw in 1807, which in 1815 became a new Kingdom of Poland ruled by Czar Alexander I, auguring a new era of national struggle. But even after 1807 many Poles continued to serve in the Imperial French Army in the four infantry regiments of the Legion of the Vistula and a number of regiments of lancers. A squadron of Lancers of the Guard even accompanied Napoleon to exile on Elba. Ironically, in the course of their service the Polish Legions often fought against other people fighting for their homeland, e. g. in Napoleon's attempt to reimpose slavery in Haiti (1803)note During which the bulk of the Poles who survived the tropical diseases switched sides and started fighting for the Haitians. After realizing that (1) the French were trying to reenslave the Haitians and (2) their expedition was almost entirely cut off from resupply from France, the Poles had both the motive and opportunity to join the side that was actually fighting for freedom. For this, the Poles were specifically granted citizenship and declared honorarily Black after Haiti declared independence and embarked on an anti-French, Black/Colored supremacist policy. A community of Polish-descended Haitians continues to exist in a few towns in Haiti. and against Spanish soldiers, guerrillas, etc. on the Iberian Peninsula.
When France and Great Britain resumed hostilities after the brief Peace of Amiens in 1803, the French army invaded and occupied the Electorate of Hanover (ruled by George III) without a fight. However, many Hanoverian officers and soldiers then left the country for England, where they formed the King's German Legion, a small army in exile consisting of all arms (infantry, cavalry, artillery etc.). The men of the Legion established themselves as one of the best fighting units of the British Army. After Waterloo, they were reintegrated into the army of Hanover.
During the early stages of the 1812 campaign, when the Grande Armée occupied Russian Lithuania, Napoleon raised a number of military units there (most of them officially part of the army of the duchy of Warsaw), offering recruits the motivation of fighting for the restoration of the autonomous duchy of Lithuania. Most of these soldiers perished during the retreat from Moscow, but a few continued to serve under Napoleon until 1814, including the tiny remnant of the squadron of Lithuanian Tatars of the Guard.
Many nationalist and anti-colonialist movements do this, especially if they also are fighting against social and legal discrimination. For instance the black former slaves and the mulattoes of the French colony of Saint-Domingue (who had very different legal status under the Code Noir, with mulattoes having a few privileges compared to blacks) eventually decided to fight for independence, seeing that the French central government was making moves to reimpose slavery, leading to the foundation of Haiti. It took a while for a general Haitian identity to develop, though. For a time the country was split into two states, one for mulattoes and one for blacks.
The numerous Polish armies in exile. Basically, every time there was fighting in the vicinity of (or over) what was Poland, each side would attempt to recruit (or conscript) the Polish to fight for them. The reward the Poles asked for was always the same: Poland.
From this experience, Poland got one of its three unofficial mottos: Za wolność naszą i waszą ("For freedom, ours and yours").
Poles did it a LOT throughout their recent history. Polish volunteers fought in the The American Revolution, The French Revolution, Napoleonic armies, in the Liberal Wars of Portugal, the Hungarian Revolution of 1848, all with the goal of eventually restoring Poland. They also signed on as Polish Legions (again) specifically against Russia on behalf of Austria-Hungary, on the condition that Austrians should support Polish independence after World War I.
Modern
The fight of the Zionists for a Jewish homeland, though they weren't actually mercenaries so much as a nation-building movement. A very large number of them fought for The British Empire (which may have issued the Balfour Declarationnote A statement indicating Britain's official support for a Jewish homeland in Palestine with the intent of Invoking the tropenote A Jewish homeland indebted to Britain would have helped secure Britain's interests in Egypt, as well as ensuring any oil that might have been there—none worth extracting as it turned out, but they didn't know that at the time. Also unknown to the British was that all of this would come back to bite them in the arse big-time, buying them as it did thirty years of dealing with Arabs and Jews fighting each other off and on that was probably orders of magnitude more costly than they imagined. Worse, they made competing assurances to the Arabs that they would have an independent Arab state including Palestine (also including Syria, Lebanon, Jordan, and Iraq; the former two were given to the French and the latter the Brits kept) if they helped Britain defeat the Ottoman Empire. So both sides were screwed over, and none too happy with them), and so many Jewish soldiers signed up for British service that there were five battalions (known collectively as the Jewish Legion) of the Royal Fusiliers composed entirely of Jewish soldiers from across Europe.
On the flip side, the various Palestinian groups opposed to Israel.
The first Czech Legion, after World War One. Their country was then merely a province of Austria-Hungary, who started the war and teamed up with the Germans. The Czechs had very little reason to fight for them, and surrendered to the opposing Russians whenever they could. Through a lot of political scheming, the Russians were convinced to raise a Czech legion of 60,000 men to fight against the Austrians. Then the Revolution broke out, and with the peace treaty between Russia and Austria, and the vicious warfare and politicking in Russia, they would not get their goal, an independent Czechia, so they turned to the western Entente. They could not leave the country through the western side, so the Entente chose to rendezvous with them in the port of Vladivostok, on the other side of Russia. They crossed the country in three years, using the railways that they hijacked, joined with the Russian White Army (a coalition of anti-Communists) and the Entente, stole the Tsar’s gold, traded it for free passage to Vladivostok with the advancing Reds when they lost, and safely sailed home, to the newly-founded country of Czechoslovakia, a social democracy.
Some of the Internationals fighting for the Republic during the Spanish Civil War were German and Italian exiles who had given up hope of returning home and instead fought to prevent fascist rule in Spain so that they might live there.
Defeated Spanish Republicans wound up fighting for the armies of various Allied countries after the Spanish Civil War. Some, like Enrique Lister, wound up fighting alongside Fidel Castro (or at least supporting his movement) in Cuba after World War II.
White Russian émigrés, most of them veterans of the Russian Revolution, formed a small unit fighting with Franco's troops against the Republic, the latter being directly supported by the Soviet government which had forced them to go into exile. Apparently, they believed that this would be the first step in liberating their country from Soviet regime.
During World War II, despite their country being under German occupation, Poland was actually one of the larger allies in terms of troops under arms in the European Theatre. At the war's end more than 20,000 ethnic Poles served under British command and more than 200,000 were under Soviet command as combat troops for the (Communist) Polish Republic, and up to 200,000 Poles served as logistics troops for the British. This is highly significant given the presence of just 100,000 ethnically 'British' combat troops (and 250,000 Anglo-Canadian-Polish combat troops under British command), 350,000 US combat troops, and 3.5 million Soviet combat troops in the European theatre in April 1945.
The Indian National Army during World War II was, depending on your perspective, either this or The Quisling, as they signed on to fight for an independent India against the British with the support of Nazi Germany and Imperial Japan.
Much the same thing with various volunteer units that the Nazi Germany raised from many Eastern European peoples, from the Baltics to the Caucasus. Many of them joined the Nazis to help "liberate" their homelands from Russian/Communist rule.
Kurds. At present they're the largest ethnic group without their own nation (at around 40 million people), though they've been trying for one since World War I. Their homeland is spread over parts of Iraq, Iran, Syria, and Turkey; and at any given point over the last 100 years the Kurds have been in some sort of armed conflict with at least one of those four nations. Some progress was made after Saddam Hussein was toppled from power in 2003 and the Kurds were granted an autonomous region in northeastern Iraq (appropriately known as Iraqi Kurdistan), but while they've mostly had no problems with Baghdad they've still had to fight off ISIS/ISIL in both Iraq and Syria, and because Kurdistan as a whole is spread across 4 nations that usually don't get along it often gets pulled into all the other conflicts going on in the Middle East.
