西行途中之艰苦难说，丘处机他们时常要受到沙尘暴、流沙的袭扰。艰难的时候，车子陷到流沙里，马儿停滞不前，人想挪动一步都很困难。丘处机的随行弟子之一赵九古甚至病死在了西行的路途上。
一路西行，多番艰难，前后三年光景，公元1222年，此时正值初夏，丘处机他们终于来到了成吉思汗的面前。蒙古士兵复奉旨意，将丘处机道长请入蒙古大帐中面见成吉思汗。丘处机帐篷阶下朝见成吉思汗。眼前的成吉思汗神情倦怠，微微抬头看了看眼前的这位叫丘处机的老道，他自阶前稳四方步而进。但见他：
头戴一顶黄纱巾，身穿筋领灰色袍。
腰系一条蓝绒带，足踏一对云头履。
手拄九节蟠龙杖，背挂一把白拂尘。
玉面光洁童子颜，苍髯颌下鬓角飘。
金精明眼似飞焰，凤眼长眉入鬓边。
行动如云随行步，逍遥稳似一散仙。
成吉思汗见之，欠身道：“真人仙踪，今喜降临，如盼甘霖。”就请丘处机道长坐一毛皮椅子上。
成吉思汗见丘处机果真是仙风道骨，十分高兴，便开门见山地向丘处机讨要长生之术和长生不老药。
丘处机道长见状，显然早已心中有数，他说道:“世上只有卫生之道，而无长生之药。”
成吉思汗半信半疑道：“传闻世人说丘处机道长有三百岁，可是否？”
丘处机道长回答：“此乃是谬传也，贫道年七十有四而已。”
成吉思汗道：“道长面色红润如童子，不是有灵药，何如此。”
丘处机道长说：“只是调养身心，作有养生之功夫，常服养气血之药精之物。大汗也可如此。大汗应安百姓为道。短命之人皆因不懂卫生之道。而卫生之道以清心寡欲为要，即一要清除杂念，二要减少私欲，三要保持心地宁静，随应天性之道。无为而治是为养生之道。”
成吉思汗闻言，沉吟了一下，有些一会地说：“真人，您的安民之道我就不明白了，您说的随天性，不错，我是信天的。可是好生恶杀？难，我想让他生，别人想让他死，我想安定，别人非要乱。我看只有以杀止杀，以乱止乱，才能立足于天地之间，清静无为怎么会达到天下大治？”
丘处机闻言，徐徐说：“大汗此想法也非首创，韩非主张以刑法刑事；商鞅主张以战止战，秦国争战了百年，虽不乏良将猛士，但终究还是没有逃脱巨鹿之败绩，咸阳之失守，此为何？”
成吉思汗闻丘处机道长所言，一时茫然无语。
丘处机继续说：“秦始皇以刑罚为巢臼，以赵高、李斯之流为手杖。然最终却难免覆巢破卵之患，倾仆跌倒之祸。可见，严刑和杀伐不可做为依靠。这是中原历朝历代一面明鉴所以有人说，事愈烦天下愈乱，法愈滋而奸愈炽，兵马益设而敌人愈多。秦国之灭亡在于措施对民众过于残暴，刑罚太严太重。”
成吉思汗听了丘处机道长此番长论，叹道：“您说的这些这事我没有听到过。神仙可以直接说说我现在应该怎么做吧！”
丘处机见状，笑了笑，道：“大汗以杀伐夺天下，然不可以杀伐治天下。以刑法除恶，以教化劝善。德刑并用，恩威并施，天下方能长治久安。”
成吉思汗琢磨着，道：“德刑并用，恩威并施。神仙是不是说我的刑和威用多了，德和恩用少了？”
丘处机道长微笑不答。成吉思汗对身边的耶律楚材说：“大胡子，请你把真人的话记下来，用蒙汉两种文字相对照，我要好好收藏，细细琢磨。”
耶律楚材点头称是。
丘处机道：“大汗常年征战，身体劳损过度，因杀生而心气暴躁，容易疾病。只有心平气和，慈悲为持戒，可得保生卫生之道。”
在后来二人朝夕相处的日子里，丘处机且不断以身边小事来劝诫成吉思汗。
有一次，成吉思汗打猎要射杀一只野猪时突然马失前蹄，可野猪却不敢扑向成吉思汗。事后，丘处机便入谏说:“上天有好生之德，陛下在圣寿已高，应该少出去打猎。坠马，正是上天告诫陛下。而野猪不敢靠近，是上天在保护着陛下。”
成吉思汗对此十分信服，告诉左右人说:“只要是神仙的劝告，以后都照做。”成吉思汗过桥时，桥一下子被雷劈断了。丘处机便说，这是上天在警告不孝顺父母的蒙古人。于是，成吉思汗就诏告国人，听从神仙的指示，要尽孝道。丘处机还多次劝导成吉思汗，治理天下之术以“敬天爱民”为本，应该体恤百姓疾苦，保护黎民生命。
公元1223年，丘处机师徒向成吉思汗辞行，从阿富汗向东返燕京，在丘处机回途中，成吉思汗一共给他发了四道圣旨，并赠给虎符玉牌，让丘处机道长的全真为掌管天下道教之教，并且免除了道院及道众的一切赋税差役。于是道侣云集，道教隆兴。从此，丘处机师徒定居在燕京之地。
其第三道圣旨和虎符玉牌内容如下:
宣差阿里鲜面奉
成吉思皇帝圣旨：
丘神仙奏知来底公事，是也煞好。我前时已有圣旨文字与你，来教你天下应有底出家善人都管着者。好底歹底，丘神仙你就便理会。只你识者。奉到如此。
癸未年九月二十四日
虎符玉牌内容：
西域化胡归顺，回至燕京，皇帝感劳，即赐虎符玉牌曰：真人到处，如朕亲临。丘神仙至汉地。凡朕所有之城池，其欲居者居之。掌管天下道门事务，仅听神仙处置，他人勿得干预。宫观差役尽行蠲免。所在官司，常切卫护。
丘处机回去之后，用成吉思汗给的玉牌救助很多受迫害的难民，收留了很多战争上遗留下来的百姓。