In 1218, after requesting Muhammad II of Khwarazm not to aid Kuchlug, Genghis Khan dispatched general Jebe with two tumens (20,000 soldiers), along with the Uyghur Barchuk (who was Genghis Khan's son-in-law) and possibly also Arslan Khan, ruler of the Karluk city Qayaliq and another son-in-law of Genghis Khan, to deal with the Qara Khitai threat, while sending Subutai with another two tumens on a simultaneous campaign against the Merkits.

The two armies traveled alongside each other through the Altai and Tarbagatai Mountains until arriving at Almaliq. At that point, Subutai turned southwest, destroying the Merkits and protecting Jebe's flank against any sudden attacks from Khwarazm. Jebe relieved Almaliq, then moved south of Lake Balkash into the lands of the Qara Khitai, where he besieged the capital of Balasagun. There, Jebe defeated an army of 30,000 troops and Kuchlug fled to Kashgar. Taking advantage of the unrest fomenting under Kuchlug's rule, Jebe gained support from the Muslim populace by announcing that Kuchlug's policy of religious persecution had ended.

When Jebe's army arrived at Kashgar in 1217, the populace revolted and turned on Kuchlug, forcing him to flee for his life. Jebe pursued Kuchlug across the Pamir Mountains into Badakhshan in modern Afghanistan. According to Ata-Malik Juvayni, a group of hunters caught Kuchlug and handed him over to the Mongols, who promptly beheaded him. The Mongols fully conquered the former territories of the Qara-Khitans in 1220.