After the Hungarian troops occupied the western Galician territories, Leszek made an alliance with Mstislav Mstislavich, Prince of Novgorod.

Mstislav supported his son-in-law, Daniel Romanovich—who had claimed Galicia since 1205—to invade Polish territories, which brought about a reconciliation between Andrew II and Leszek.

[6][7] Initially, he supported Roman Mstislavich's minor sons, Daniel and Vasilko Romanovich, against Vladimir Igorevich and his brothers, who also claimed Galicia.

[8] 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.

[10] Andrew returned to Hungary, but only after appointing a Galician boyar (or nobleman), Vladislav Kormilichich, to lead the Hungarian army to Galicia.

[12] 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.

[13][14] In a letter to Pope Innocent III, Andrew stated that Galician boyars had proposed him to grant Galicia to Coloman.

[note 1][16][17] 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.

[24] Pope Honorius III mentioned in a letter in 1222 that the Archbishop of Esztergom had crowned Coloman "with the blessing of the Holy See", but the circumstances of the ceremony are unknown.

[26][29] Mstislav invaded Galicia between 1215 and 1219—most probably in early 1219, according to Font and Barabás—and forced Coloman, Benedict the Bald and Sudislav to flee to Hungary.

[30][31] Mstislav gave his daughter, Anna, in marriage to Daniel Romanovich who soon occupied the lands between the rivers Wieprz and Bug from Leszek.

[35][37] Andrew most probably made Sudislav's son-in-law, Philnius, the commander of the Hungarian army in Galicia around this time, according to Font and Barabás.

[33] Mstislav's fiasco encouraged Philnius to join Leszek's campaign against Volhynia, leaving Coloman and Salomea in the newly fortified Church of the Virgin Mary in Galicia.

[33][35] Taking advantage of the absence of the bulk of the Hungarian army, Mstislav and the Cumans laid siege to Galicia in August 1221.

[note 2][36][39] Philnius hurried back from his campaign, but Mstislav defeated his army and he could only flee with the help of a Galician boyar, Zhiroslav on 14 August.

[44] A late source (a 1279 letter of Elizabeth the Cuman) mentioned that Coloman had held Szepes till the end of his life.

[50] Coloman's jurisdiction also included counties located in Hungary proper, such as Baranya, Pozsega, Somogy, Valkó, Varasd and Zala.

[56] The three prelates persuaded Coloman to confirm the knights' privileges on 31 July 1231, but a full reconciliation was reached only after lengthy negotiations in 1239.

[58] Coloman initiated the merger of the Archbishopric of Split and the Bishopric of Zagreb, but Pope Gregory IX reminded him in 1240, that the two dioceses could not be united without the consent of the archbishop of Kalocsa and the chapters of their sees.

Coloman, similarly to his brother, opposed his father's third marriage with Beatrice d'Este and following the death of King Andrew II (21 September 1235) they accused their young stepmother of adultery.

[citation needed] Pope Gregory IX persuaded him to pursue the heretics in his provinces and in the adjacent territories; therefore he invaded and occupied Bosnia and Zachlumia but he could not wind up the Bosnian Church.

[citation needed] Coloman was styled "by the Grace of God, king of the Ruthenians, and by his glorious father's generosity, duke of Dalmatia and Croatia" in his first extant charter in 1226.