Before the Mongol conquest in 1279, numerous envoys were sent from the Southern Song court to its neighboring states. Their purpose was to evaluate and tame foreign territories and alien peoples and thereby reduce their threat to Song culture, and the travelogues resulting from these journeys were often “utilitarian” in style. The Record of the Perfected Master Changchun's Journey to the West (Changchun zhenren xiyou ji 長春真人西遊記), however, deserves special attention for its nuanced handling of a complex cultural-political power dynamics. Its compiler, Li Zhichang, was a leader in the Quanzhen sect, and his travelogue documents the journey of his master, Qiu Chuji, at the invitation of Chinggis (Genghis) Khan. Li's text illustrates the tension of competing political and cultural authorities: while the Mongols were becoming the source of political authority, the Taoists still owned the discursive power. The author argues that Li deliberately adopted a narrative strategy that conceded the Mongol claim to political legitimacy while simultaneously asserting Taoism's cultural dominance over the Mongols. The article also juxtaposes Li's work with the travel record by Yelü Chucai, a Khitan adviser to the Mongols who traveled with Chinggis Khan during his western military expeditions. Although Yelü's travelogue is often read as a rebuttal to Li Zhichang's work, a closer look reveals how Yelü appropriated Li's strategy for his own agenda: to justify Mongols' invasion of Central Asia while highlighting the cultural values shared between the Mongols and the Han Chinese. Both works employ rhetorical strategies that laid the foundation for political discourse affirming the Mongol-Yuan dynastic legitimacy.