忽必烈沉吟了片刻，非常果断地说他准备任命他们为访问教皇的专使，陪同一名特使立即出发。他们的任务有两个，一是带一封信给罗马教皇，同时请求教皇选派100名既通基督教教义，又熟谙修辞、逻辑、文法、数学、几何、天文、音乐等七艺的学者；二是要求波罗兄弟返回元朝复命时，带一点耶路撒冷墓前的圣油回来。为了保证他们行程的安全，忽必烈特意赐给他们一枚金牌，凡持有这种金牌的人和他的所有随行人员，在元朝境内，一切地方官吏都必须保证他们的安全，按站护送；他们行程所经之地，无论大小城镇、寨堡村庄，都必须保证供应他们的一切必需品。
1266年，经过了充分的准备之后，波罗兄弟和特使及随行人员启程了。谁知走了不到20天，特使就一病不起。波罗兄弟进退维谷，一筹莫展。最后商议的结果是，波罗兄弟俩接过特使的任务，告别其他人，踏上了回乡的路途。由于波罗兄弟带着忽必烈的金牌，沿途省去了很多的麻烦。但是，恶劣的自然环境给他们制造了巨大的困难，严寒、风雪、洪水，让他们疲惫不堪。一共花了三年的时间，才到达了亚美尼亚的海港城市来亚苏斯。
波罗兄弟在向他们的亲人们描绘这一切时，兴奋异常，激动之情溢于言表。谁能想到去的时候，他们只是两个满脑子黄金梦的威尼斯商人，回来时居然成了肩负重任等待谒见教皇的特使。别说是波罗兄弟俩，就是家里的亲人们也为之欣喜欢呼，至于马可更是高兴得忘乎所以。
“可惜好运不可能一直走到头。”尼可罗的这句话给大家劈头浇了一瓢冷水。
原来教皇克莱门特四世已经于1268年去世了。波罗兄弟刚到达阿克城就听到了这个噩耗。他只好去找在阿克城内的教皇派驻巴勒斯坦的特使特巴尔多·威斯康德。威斯康德非常仔细地听取了波罗兄弟的报告，他既兴奋又有几分无奈。兴奋的是这个消息对于基督教国家来说无疑意味着一个很有利的机遇；无奈的是新教皇即位，起码得等上相当一段时间。如果没有教皇的许可，这件事就无法进行下去。于是，威斯康德劝波罗兄弟先回到威尼斯，静候新教皇的诞生。别人听了这番话兴许觉得有点扫兴，但马可依然信心十足，他不停地为父亲和叔叔鼓劲打气。
就这样，马可天天缠着爸爸和叔叔讲述他们的东方见闻。他从中知道了许多地中海以东直至遥远的蒙古帝国的事情。
“将来如果有机会，我一定要亲眼去看一看东方是个什么样子。我也要去东方做一次充满刺激充满乐趣的旅行！”
波罗家族遗传下来的勇敢冒险的精神在马可的血管里一次又一次地涌动。渐渐地，马可产生了一种强烈的甚至连做梦都向往到亚海去旅行的愿望。
爸爸和叔叔回到威尼斯已经将近两年了，可是还没有听到新罗马教皇确定下来的消息。新罗马教皇定不下来，就实现不了对忽必烈可汗的允诺，就不能到东方去旅行。这使马可非常焦急。他有时恨不得一下子飞到东方，飞到亚海去。
这一天晚上，爸爸和叔叔又摇着头叹息着从外面回到家里。马可一望就知道他们又去打听罗马教皇的事了，肯定还没有确定下来。马可也变得沉默寡言闷闷不乐了。他萎靡在床上，无心听爸爸和叔叔的抱怨，独自想着心事。不知不觉地进入了梦乡。
尼可罗和马窦正谈话间看到马可安然地睡着了，他的脸上还浮现着满足的笑容。
“恐怕这孩子将来也想随我们一起去亚海呢………”
临行的日子终于到了，马可一行三人在亲人们的眼泪和叮咛中离开了码头，马可站在船尾，默默地望着渐渐远去的威尼斯，心里暗暗念着：“别了，威尼斯，愿圣马克保佑我们。”刚才菲亚的热烈拥抱，朋友们羡慕的目光似乎就在眼前。
船飞快地向亚约里亚海驶去，他们沿着达尔马希亚海岸，经过尤利西斯岛，希腊的伯罗奔尼撒，克利特，塞浦路斯。在该途的几个重要的商业海港，他们都做了短暂的停留，一边做些买卖，一边了解近东最近的形势，沿途的社会风情，人文地理，使得马可为之激动不已，他庆幸自己坚决要求随父亲同行的决定是多么正确，否则就会像一只井底之蛙坐井观天。
每一个新的事物，每一次新的发现，都让马可惊叹，他特意买了不少羊皮纸，专门用来写旅行日记，尼可罗看着马可天天晚上在灯下埋头笔耕时，总是显出一副不屑的神情。
经过匆忙跋涉，他们终于到达了地中海东岸的阿克港，然后又取道莱西斯城几经波折来到了西莫尼亚（今天的土耳其），然后进入波斯穿过了灼热的沙漠地带，赶到了北边的克尔曼城。
对于旅途的艰险，马可他们有着充足的心理准备。他们经过艰难的跋涉穿过克尔曼，越过科比南城，又先后经过巴尔赫、巴尔赫尚等地，一路东行来到了帕米尔高原的山脚下。
马可随父亲第一次进行长途旅行，虽然有着坚强的意志，但是毕竟没有经历过大风大浪的洗礼，他的身体逐渐被拖垮了。
来到帕米尔高原根部的时候，人们发觉马可的身体极度虚弱，脸色灰暗。
马可病倒了，一病就是半月有余。尼可罗和马窦看到马可的身体虚弱已不适于长途旅行，就决定在这里好好地休养一番。
马可休养身体期间，他并没有让时光白白地浪费掉，而是以一个商人的习惯了解了这一带的风土人情及物产等。他注意到这一带出产珍贵的红宝石和金银等矿产，还了解到这里的人们种植小麦和芝麻等农作物，并出产核桃等。
马可对这里最感兴趣的是，当地人经常用弓箭到野外狩猎野生动物，然后就用狩猎到的动物的皮毛制成柔软漂亮的衣服。马可非常喜欢这些衣服，穿在身上舒适温暖。于是他同尼可罗商量买下了几件。
“我们翻越常年积雪的帕米尔高原可能用得着这些皮毛衣服呢。”
尼可罗非常欣赏马可的远见卓识，对马可大加赞赏了一番。
经过一年的休养，马可的身体完全复原了。由于他经常锻炼的缘故，看上去他的身体比以前更健壮了。
终于他们决定翻越帕米尔高原了。
马可站在高高的山巅之上，白云在身边缭绕。不远处的两山之间，卡拉库鲁湖像一面明镜镶嵌在大地上，又像一位美丽的少女默默含羞不语。一条美丽的河流从湖上发源，蜿蜒地穿越一块辽阔的平原。平原上绿草如茵，一群群野羊正在撒欢。马可抬起头来，极目远眺，四周崇山峻岭，高接云天。
一片白云从他的眼前飘过，马可真想伸手把它抓过来，当纱巾围在脖子上。这就是世界上最高的地方！我征服了它，他把手伸向蓝天。是征服了吗？身处在真正的天地之间，马可突然感到了自然的不可战胜，感到了它博大的胸怀，感到自己真像是一粒芥草，在它面前是如此的渺小无力。要认识它都这般艰难，何谈征服二字，马可暗自叹息着。
马可意识到问题的严重性，不再去研究地形地势和动植物了，和两个向导专心赶路。
海拔越来越高，山势也越来越险峻，崎岖的山路蜿蜒曲折，高山的巅峰之上是一片银色的世界，寒风在山谷中呼啸，隆冬似乎在一夜之间就降临在他们面前。向导告诉马可，这才是真正的帕米尔高原。
高原上极为荒凉，渺无人烟，甚至连一只飞鸟都见不到，马可觉得简直像被扔进了地狱，生命气息的飘失令他恐惧。
万幸的是，他们带足了路上食用的一切物品，否则除了石头和泥土，没有任何东西。
山在变高，空气在变稀薄。每个人的腿都像灌了铅似的，只听得阵阵呼呼的喘气声。马可看着父亲和叔叔那惨白的脸，看着他们迈着无力的步伐向前挪动，心里非常焦急，谁要是在这鬼地方生病，真是一点办法都没有。由于氧气含量少，燃烧点低，食物永远是半生不熟的，水也是温吞吞的，他们本已衰弱的体力，更无法得到补充。
十二天之后，马可终于感到是在向下走了。他们攀越连绵起伏的莽莽群山，涉过弯弯曲曲的河川细流，穿过人烟绝迹、寸草不生的茫茫沙地，足足用了40天时间，来到了帕米尔高原南方的吉吉特。
苍茫的灰色在逐渐隐去，片片绿色洒在大地上。万物复苏，重回人间。马可骑在马上大声地喊叫，他第一次感到绿色就是生命。
块块农田，片片葡萄园，袅袅炊烟，隐隐传来的牧羊人的歌声。
到了，这就是著名的西域，蒙古帝国的发源地和中心。
正当马可一行人满怀着憧憬向着元朝快速前进的时候，却突然发现正前方有异常情况。只见前面的大路上烟尘飞扬，马蹄声声。一大队人马飞快地朝他们奔来。
马可他们都很紧张，一个个剑拔弩张的样子。尼可罗见状，大声地告诫人们：
“如果是强盗，他们要什么就给他们什么，谁也不许反抗！”
马队越来越近了，连骑马人的模样都能看清楚了。原来是元朝的一队骑兵。队伍前一面金黄色的大旗迎风飘摆，猎猎作响。马背上是一个个身穿金盔金甲的武士，他们都雄纠纠气昂昂的样子，愈发显出他们的勇武和剽悍。马队来到近前，见马可他们都是外国人的打扮，便勒住马停止前进。从马队里走出一个军官模样的人，催马来到马可他们的面前问道：
“你们是从威尼斯来的波罗家族的人吗？”
“正是！”
“我是奉了忽必烈皇帝的圣旨前来迎接你们的，快随我登程去拜见忽必烈皇帝吧！”那个军官高兴地催促着马可一行。
马可他们弄清了马队的来意，心里的恐惧感立刻就烟消云散了，代之而来的是满心的欢喜。因为这样一来，马可他们就再也不用担心会有强盗来骚扰他们了。
马可虽然为以后再也不用过担惊受怕的日子而高兴，可他心里还有一个结没有解开，那就是伟大的忽必烈皇帝怎么知道他们来到了元朝的地界了呢？
原来，自从尼可罗和马窦离开元朝返回威尼斯以后，忽必烈皇帝就经常派人打探他们是否有赶回来的消息。当马可他们到达甘特以后，甘特的官员早就把他们的消息派快马千里迢迢地报告了忽必烈。忽必烈皇帝闻听大喜，即刻派了一队人马赶来甘特接应马可一行。凑巧的是，两拨人马在半路相逢了。
马可一行在元朝军队的保护下，顺利地到达了元朝的上都（即现在的内蒙古自治区的多伦），见到了元朝的皇帝忽必烈。
异乡为官路
马可一行历时三年半的时间，经过了千辛万苦的跋涉，终于在1275年到达了元上都，见到了忽必烈。这一年，马可满21岁。
元朝的上都被高大的城墙围绕着，足有25公里长。皇帝的宫殿都是用大理石砌成的，美丽雄伟壮观。马可被东方的美妙建筑艺术惊呆了，他认为这简直就像仙楼琼阁一般。走进宫殿，房屋装饰得金碧辉煌。尤其是房间里悬挂着的书法、绘画艺术品，透着一股泌人心脾的墨香味，让人留连忘返。
殿阁之间有回廊曲苑相连，这些走廊0也被装饰得美妙非凡。从走廊向外望去，庭院里青松古柏，修竹异草，处处显示出环境的幽雅与高贵。
马可、尼可罗和马窦三人，很快被领去见忽必烈皇帝。宫殿的走廊里铺着红色的厚厚的地毯，走上去柔软舒服。他们被领进一座最宏伟的宫殿。只见忽必烈皇帝高高地坐在龙椅上，两厢站满了文武大臣。
马可他们急忙跪倒在大殿之上，双手举着献给忽必烈皇帝的贵重礼物——水晶杯、五彩玻璃球和圣灯油等。
忽必烈高兴地收下了他们的礼物，并赞赏了他们一番，并且很感兴趣地询问了沿途的情况。可是尼可罗和马窦除了路途如何艰险外，说不出多少东西，因为他们心思多半放在生意上了。倒是马可用简明易懂的语言，条理清晰地叙述了一切的经过情形。阿雅斯的情况、玛木路库的史坦丁·拜巴鲁与小亚美尼亚的战争、阿津甘的喷油井、大不里士的商业、起而漫的军工制造业、忽里模子港、巴拉香宝石、帕米尔高原的险峻、西域风情以及罗布大沙漠的恐怖，等等，甚至于沙洲的殡葬仪式、哈密以妻女陪客的怪俗，几乎所有的人都被吸引住了。沿途的地形、军事要塞、行路所用时间，马可表述得清清楚楚。
忽必烈的眼里溢出柔和的笑意，他对马可惊人的记忆力和语言能力、对人文地理精确的判断力极感满意。马可告诉了他许多急于想知道的情况，因为当时海都举兵叛乱，军事威胁日益加甚，就在这年的正月，诸王火忽响应海都，南疆一带几乎失控，东西交通常常断绝。而伊利汗国和元朝关系密切，旭烈兀曾在忽必烈的汗位争夺战中坚定地站在他一边，有效地牵制住了阿里不哥及窝阔台汗国诸王。但是，伊利汗国与撒拉逊人的交战情况因交通不畅而一直不甚明了。马可的详细报告，解除了他心中很多疑问。
忽必烈高兴地对站立在下手的宰相安童说：“宰相者，明天道，察地理，尽人事，兼此三者，乃为称职。马可先生堪称是一个活地图，有几个人能走过朝廷如此多的疆域而详察地理人情呢？”他对马可说：“你要尽快把这些情况写出来，交给安童大人。朕很满意你的忠诚、热心和勤奋，特命你为怯薛，随侍朕的左右。”他又赏赐了尼可罗和马窦很多珠宝。马可他们立刻跪下谢恩。朝堂上响起一阵轻微的议论声，所有的人对忽必烈给予这些威尼斯商人的重赏感到有点惊讶，尤其是对马可的重用。
怯薛是由蒙古贵族和其他民族的高级官僚以及地方官之子弟充质子者充当，是世袭制。怯薛是宫中近侍，最接近皇上，并公开活动于内廷与外朝之间，口传圣旨，出使地方，甚或出任高官重职。马可可算是一步登天了。
马可得以重用，一方面是因为他出众的才干；另一方面也是由于前几年发生的叛乱，忽必烈对汉人心生猜忌，转而重用色目人。
