尼可罗、马飞阿一得到教皇代表的信后，带着马可，立即动身朝阿雅斯港进发。这段行程平安无事，连大一点的风浪都没遇到。除了害怕遇到热那亚人的船队，别的似乎没什么可担心的。
尼可罗和马飞阿天天在船内忙于清点货物，整理账目。马可则跟着船长，一招一式地学习航海，或者就是坐在船头，埋头在他的羊皮纸上写着什么。
濒海地区的阿雅斯，是一座巨大的商业港口，也是热那亚、威尼斯以及其他各地商贾的云集之地。这里同样是各种香料、药材、丝绸、毛织品和其他珍贵商品的交易、集散港口。有些准备到地中海东部各国山区的旅行者，往往也取道于此。
金秋时节的阿雅斯港是一年之中最繁华的时候，生意兴隆通四海，财源茂盛达三江，用这句中国名言来形容，恐怕是最确切不过了。波罗兄弟俩在这里停留了好几天，津津乐道于做生意，他俩将威尼斯带来的大部分货物卖了出去，而且还卖了个好价钱，同时也买了一些当地的土特产。马可看着他们乐不思蜀的样子，非常吃惊他们怎能把使臣和商人这两者截然不同的身份绝妙地糅合在一起。
等波罗兄弟恋恋不舍地离开阿雅斯来到小亚美尼亚王国的都城塞巴斯托茨时，已经是1271年10月上旬了。
塞巴斯托茨城并不大，但是戒备森严，城外碉堡林立，城门被士兵严密地把守着。马可看到这种情况，心里非常紧张。马飞阿告诉他，小亚美尼亚境内实际上是蒙古人和撒拉逊人的缓冲地带，它的南部边境地区，土地肥沃，物产富饶，现在被撒拉逊人控制着；它的北部是卡拉马尼亚，居民主要为土库漫族；而它的东北部是恺萨里亚，塞瓦斯塔和其他一些属于蒙人的城市；西部地区面临大海，与克里斯坦栋海岸隔海相望。
尼可罗很严肃地看着马可：“你明白了？这里的局势很复杂，我们只能说自己是威尼斯来的商人，其他一概不要多说，免得招来不必要的麻烦。”
“放心吧，我会很谨慎的。”马可回答道。
他们进城后，找到驿馆，因为驿馆比普通客栈要安全得多。恰好当时没什么人，很顺利地就住了下来。尼可罗和马可忙着解行李，安顿住房，马飞阿则去吩咐伙计给马匹喝水和喂草料。
第二天早上，正当他们在房里一边吃早餐一边计划着下一步的行程时，忽然听到一阵急速而杂乱的脚步声直冲他们的房门，马飞阿一下从椅子上蹦了起来，伸手就去抓放在床上的宝剑，尼可罗制止了他，门被猛地推开了，进来了几个人。
“你们是从意大利来的吗？”为首的一位官员说。
“是的，大人。”尼可罗很谦和地回答道。
“是波罗先生？”这位官员的口气缓和了不少。
尼可罗点点头。
“总算找到了，快随我们进宫去，”官员催促道。
三人忐忑不安地跟着这几个人向王宫走去。一路上他们试图用各种方式从那位官员口中套出为什么要赶到王宫去的原因，可面容古板的小亚美尼亚人拒绝回答任何问题。
进了华丽的宫门后，那位官员停下脚步，两名侍卫迎上前来，同样是一言不发地将他们领上大殿。尼可罗、马飞阿和马可低着头，紧紧跟着侍卫。
小亚美尼亚国王李昂三世坐在高高的镶金嵌宝的王座上，左手慢条斯理地摸着嘴边的胡须，台阶下左手边的几把椅子上坐着几位王公大臣，右手边坐着五位风尘仆仆的男人。尼可罗等三人恭恭敬敬地向国王鞠了一躬。
“是他们吗？”李昂三世细声慢语地问道。
“是。”侍卫回禀道。
右手坐着的三位站了起来，马可一下认出了为首的是教皇的代表特巴尔多的秘书，还有一位也是他们见过的特巴尔多官邸的警卫，他简直不敢相信自己的眼睛。
“你们肯定非常奇怪会在这里见到他们，很简单，他们是信使，你们必须马上赶回阿克。”李昂三世望着惊愕不已的三位威尼斯人露出了一丝笑意，“你们刚离开阿克城不久，枢机主教会议推选教皇代表特巴尔多·威斯康德为新教皇，9月1日已经正式即位，成为格里戈里十世。教皇命令他们三位来追赶你们，如果你们还在我境内的话。我已准备了一艘军舰，马上动身，向教皇复命。另外，我派一位大臣作为特使，专程前往阿克，谒见并恭贺新教皇。”
尼可罗他们听到这个消息，喜出望外。辞别国王后，随即跟随大队人马匆匆起程。
来到阿克城里，正值傍晚时分，格里戈里十世立刻召见了他们。觐见大厅里空荡荡，左墙上挂着几幅圣像和一个耶稣蒙难的银十字架，右墙上的托架里，点着蜡烛和火炬，照亮了整个厅堂。
新教皇低头沉思着，他的衣着一如从前，只有手上的加冕典礼上赠与的教皇戒指，显示出特巴尔多已经变成了格里戈里十世。
三位威尼斯人在圣教会的领袖面前跪了下来，尼可罗轻声说道：“教皇陛下，我们回来了。”
教皇格里戈里从沉思中抬起头，举起手向他们问好，示意他们站起来：“这真是一个奇妙的改变，现在终于可以做以前想做而无法做的事情了。我要你们把上次我写给忽必烈汗的那封信退给我，我会重新写一封信。”教皇沉吟了半晌，想说什么又没说，“先休息吧，会很快召见你们的。”
将近三年时间教皇的空缺，使得格里戈里就任伊始，头绪繁杂，异常忙碌。和蒙古人的关系问题事关重大，他需要时间静下心来思考一下。
为了夺回自637年被回教国家占领的圣地耶路撒冷，从11世纪末，西欧的封建领主及诸王们发动了一系列的十字军东征。第一次十字军东征，恰好位于小亚细亚和叙利亚的撒答鸠克王朝与埃及的法蒂玛王朝发生纷争，十字军乘隙而入，获得成功。但不久后，在法蒂玛王朝中出现了一位阿拉伯英雄，他就是日后建立阿尤库王朝的萨拉丁。萨拉丁给十字军以沉重打击。之后的一系列东征虽然有些战果，但在回教国家的反击中又基本丧失。1244年，耶路撒冷再度失守。
1250年，阿贝克在埃及建立了玛木路库王朝，它那异常精锐的玛木路库军屡次大败十字军，十字军最后的要塞阿克形势趋于危急。想到这里，教皇吸了口气，轻轻摇了摇头，这几年来，他虽是教皇代表，也只能困守孤城，无可奈何。
波罗兄弟的东方之行勾起了他的满腹心事。此时距上次蒙古西征已经有近30年了，现在回想起来，蒙古铁骑狂扫一切的洪流令人不寒而栗，这座火山是否会再次喷发呢？传说中的基督徒普瑞斯特、约翰和达维特王究竟情况如何？真是谜一样的东方。波罗兄弟之行，可能是一次难得的机会。
几天之后，一间小小的密室里，当尼可罗、马飞阿和马可被秘书带进去时，室内的凝重气氛让他们觉得有点喘不过气来。屋子中间有一张桌子，桌子上放着镶有宝石的圣像和几个雕刻精美的水晶花瓶。
门开了，教皇格里戈里走进密室，身后跟着两个多米尼克派的修士。三个人赶忙鞠躬致敬，教皇举止随便，亲切随和，好像又是特巴尔多了。
教皇示意他们坐下，用手指指桌上的那堆东西：“这是我挑选出来送给忽必烈汗的礼物，这些精美的工艺品我想会给他留下深刻印象的。圣油有了，礼物也准备好了，信马上就交给你们，可以动身了。至于大汗要求派一百名既精通基督教教义，又熟谙工艺的学者，恐怕我无法满足他的要求，我不知道怎样去找到，在什么地方找到这些人。不过我还是找到了两位学识渊博、勇敢正直的人。”
教皇分别介绍了两位修士，体格健壮的一位是维琴察·尼古拉修士，身材瘦小一点的是的黎波里的威廉修士。这俩人简慢地向尼可罗和马飞阿问了好，马上又摆出一副自视甚高的样子，对年轻的马可连看也没看一眼，马可不禁有点愤愤然。
教皇告诉他们，他已授予两位修士权力证书，有权赦免并有权以教皇的名义，任命神父和主教。
“我希望你们，”教皇看着大家，“平安地将我的信交给他，让我的声音在他的耳边回响。你们不仅是建立联系，更重要的是保持友好的关系。这样起码可以让他们持守中立，也有利于教会事业的发展。如果蒙古人能和我们共同对付撒拉逊人，那么事实上，伊利汗国和基督教世界的国家关系一直尚好，他们的阿八哈汗曾给教皇克莱门特写过信：而英国国王爱德华一世也曾约请阿八哈汗出兵共同向叙利亚地区夹击，后来因为伊利汗国和察合台汗国正发生战争，就此作罢。记住，用你们的眼睛，用你们的耳朵。我们解放圣陵的计划可能更容易实现。”
“尊敬的陛下，”尼可罗感到很为难，“我们只是威尼斯的平庸的商人罢了，如此重大的任务……”
“你们能做到。”教皇打断了他的话，“因为你们和大汗有着良好的关系，他信任你们。这是任何人所无法替代的，你们并不是教会第一次派出和蒙古人打交道的。早在1245年，为了保护岌岌可危的基督教世界，教皇英诺森四世派遣柏朗嘉宾出使蒙古，他于次年7月到达和林并觐见了遗由大汗，还带回了遗由给教皇的一封信。第二次是1253年，鲁布鲁克奉法兰西国王圣路易九世之命，通过钦察草原去见蒙哥汗，他曾想留下传教，结果被拒绝了。他们俩个都写了详尽的旅行报告，可惜有很多我们依然一无所知，因为他们毕竟是浮光掠影而过。”
“我希望这次能让我们多了解一些，这很有好处。”教皇的命令，让波罗兄弟觉得诚惶诚恐，而马可却感到热血在胸中奔腾。
教皇看着马可激动的样子，微微一笑，轻声对他说：“我同样寄希望于你。”教皇对马可留下了极好的印象，这位青年人机敏、谨慎、细致，他相信自己不会看错人。临行前，教皇破例为他们三个俗人祝福。三个人再一次跪谢了教皇。
当初，波罗兄弟是以忽必烈汗特使的身份去见教皇，而现在又以教皇使节的身份去见忽必烈，可以说是具有双重身份。由商人突然成了肩负重任的秘密使节，这个变化让兄弟俩一时难以适应，马可则暗自庆幸当初坚决要求同行的选择是多么正确，他觉得今天夜晚，为他的人生翻开了崭新的一章。
