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.