一切基本就绪后，波罗三人立刻动身前往亚美尼亚的莱亚苏斯港准备返回蒙古帝国，三年前波罗兄弟也是从这里踏上了回家之路。虽然莱亚苏斯港面积狭小，但马可称：“这里云集了来自威尼斯、波斯、热那亚和所有内陆地区的商人，为了方便做生意，商人们在这里兴建了很多货仓。”

就在他们即将动身的时候，这里突然爆发了一场叛乱，马可说：“为阻止敌人的围追堵截，成吉思汗的一个孙子命人在沙漠中开挖出很多战壕和地沟，导致多条主要道路被毁。”

这次叛乱将波罗三人困在了莱亚苏斯。就在他们无奈地等候平息叛乱的同时，一位罗马教廷的信使给他们带来一个惊人的消息：1271年9月1日，在经过有史以来最长的一次酝酿，枢机主教们终于选出了新的教皇，而新教皇不是别人，正是他们熟悉的泰奥巴尔多。马可称：“兄弟俩听到这个消息后高兴不已。”

信使同时还带来新教皇的命令，让他们返回阿迦。于是，在武装护卫下波罗三人重新回到了阿迦城。这次去阿迦，波罗兄弟可谓收获颇丰，已身为基督教界最高领袖的泰奥巴尔多设宴款待了他们。教皇还仔细考虑了忽必烈提出的心愿，认为这是在蒙古帝国尤其是在整个中原地区传播基督教的一次很好的机会，于是教皇同意派出两位修士与波罗三人同行。按照马可的叙述：“这两位修士是整个主教区最为博学和高尚的人。”他们享有很多特权，而且“在教皇的权利范围之内，这两位修士可以不受限制做很多事，甚至可以像教皇一样任免主教和牧师。教皇还让两位修士带上送给蒙古大汗的水晶、珠宝及其他礼物”。总之，朋友荣升为教皇并因此给他们带来这么多好处对波罗兄弟来说，的确是一件幸事。于是他们满怀憧憬地踏上了东去的征途。

征途总有波折。在途经亚美尼亚时，波罗三人触犯了当地的首领比巴拉苏丹。比巴拉扬言要监禁三人，两位修士出于安全考虑拒绝再与他们同行，但是波罗三人已经为此事历经千辛万苦并耗费了大量时间，所以他们是绝不会轻易放弃的。三人一致认为，可以和部落首领通过谈判来解决问题，当然最管用的还是用珠宝贿赂他们。最终，虽然没有了教皇侍卫的陪同，尼科洛、马费奥和马可仍然坚持东进。

1272年3月27日，泰奥巴尔多在罗马被正式封为格里戈里十世。而此时，为了教廷、为了蒙古帝国和东西方微妙复杂的关系，波罗一行三人正在遥遥无期、风险莫测的旅途当中艰难跋涉。

在基督教徒看来，他们三人在各种极为不利的条件下坚持去东方，无异于踏上了一条不归路。成功的机会微乎其微，如果真能生还绝对是个奇迹。

然而，波罗三人的看法却截然相反。他们深信东方遍地是贸易机会，并且只要做事稳妥就一定会有收益。他们以商人自居，而不是把自己当作基督教的卫道士或者使者。在他们看来，贸易可以冲破一切文化差异和冲突的阻碍，而他们正好可以利用这次机会将自己的想法通过实践来进行检验。如果想法是正确的，那么他们将荣归故里，声名显赫。如果想法错误，他们将从此隐姓埋名，不为人知。

尼科洛和马费奥单膝跪地向忽必烈献上了教皇的书信