After the Hungarian troops occupied the western Galician territories, Leszek made an alliance with Mstislav Mstislavich, Prince of Novgorod. Mstislav invaded Halych, forcing Coloman and his supporters to flee to Hungary, most probably in early 1219. Mstislav supported his son-in-law, Daniel Romanovich—who had claimed Halych since 1205—to invade Polish territories, which brought about a reconciliation between Andrew II and Leszek. The Hungarians and Poles again occupied Halych and restored it to Coloman in the autumn of 1219. Mstislav and his Cuman allies defeated the Hungarians near Halych and captured Coloman and Salomea in August 1221. To secure their release, Andrew II renounced Halych and arranged a marriage alliance between his youngest son, Andrew, and Mstislav's daughter.
Coloman returned to Hungary in late 1221 or 1222. He settled in Szepes (now Spiš in Slovakia) where he had held large estates since the late 1210s. Andrew II made him duke of Slavonia, with jurisdiction also in Croatia and Dalmatia, in 1226. He cooperated with his eldest brother, Béla, in revising their father's donations already during Andrew II's lifetime.
Coloman was the second son of Andrew II of Hungary and his first wife, Gertrude of Merania. Andrew's father (Coloman's grandfather), Béla III of Hungary, was the first king of Hungary to conquer the Principality of Halych in 1188. Béla granted Halych to the teenager Andrew, but Andrew was unpopular, especially because his troops did not respect the Galicians' Orthodox faith. The Galicians expelled him in 1189 or 1190, but he did not abandon his claim to Halych. After Roman Mstislavich, who had united the principalities of Volhynia and Halych under his rule, died fighting against the Poles in 1205, Andrew launched a military campaign against Halych in almost each year. He adopted the title of "King of Galicia and Lodomeria" in token of his claim to both principalities. Initially, he supported Roman Mstislavich's minor sons, Daniel and Vasilko Romanovich, against Vladimir Igorevich and his brothers, who also claimed Halych.
Coloman was born in 1208. According to historians Márta Font and Gábor Barabás, he was named most probably for Coloman of Stockerau, an Irish pilgrim who had been martyred in Austria in 1012. Coloman's mother showed blatant favoritism towards her German kinsmen and courtiers, which outraged the native lords. She was murdered by a group of Hungarian noblemen in September 1213, shortly after her husband departed for a new military campaign against Halych. Andrew returned to Hungary, but only after appointing a Galician boyar (or nobleman), Vladislav Kormilichich, to lead the Hungarian army to Halych. Kormilichich took control of the principality on Andrew's behalf. Leszek the White, Duke of Poland, granted asylum to Daniel and Vasilko Romanovich and made an alliance with princes Alexandr Vsevolodovich of Vladimir and Mstislav Yaroslavich of Peresopnytsia. They invaded Halych and routed Kormilichich, but they could not capture the capital of the principality.
In a letter to Pope Innocent III, Andrew stated that Galician boyars had proposed him to grant Halych to Coloman. According to the Galician–Volhynian Chronicle, Leszek the White was the first to suggest the same idea, also proposing his daughter, Salomea, to Coloman. Andrew and Leszek had a meeting in Szepes in the autumn of 1214. They reached a compromise, which included the marriage of Coloman and Salomea and the cession of two western Galician towns, Przemyśl and Lubaczów, to Leszek. The Hungarian and Polish armies invaded the principality and put an end to Vladislav Kormilichich's rule before the end of the year.