在向导的指引下，朝圣者们在各个圣殿之间奔走往来。
为了争夺通向这些圣殿和圣物遗迹的道路及其所属权，穆斯林和基督徒之间的摩擦不断。
波罗兄弟也加入了朝圣者的队伍来到位于奥利弗山下的圣墓为忽必烈汗取灯油。
尽管研究圣经的学者们对圣墓是否真是耶稣的墓地持怀疑态度，但是教徒们对这里依然充满敬仰，包括波罗三人，他们从来都没有怀疑过圣墓的真实性。
鲁道夫谈到这座位于今天耶路撒冷旧址的圣墓时，说：住在圣墓教堂里的古格鲁吉亚人掌管着圣墓礼拜堂的钥匙，所有的食物、供奉物品、蜡烛以及圣墓的照明灯油都是朝圣者们从教堂南门的小窗送进来的。
和所有的朝圣者一样，波罗一行慷慨捐赠后也领到了灯油。
然后，他们便以最快的速度返回了阿迦城。
他们不在阿迦城的这段日子，没有什么太大的变化。
泰奥巴尔多告诉他们，尽管经过了两年多的酝酿，但枢机主教们依然没能选出新的教皇。
因为兄弟俩已经得到了灯油，所以他们不想再漫无目的地等下去，而是打算马上返回蒙古帝国向忽必烈汗复命。
兄弟俩恳请泰奥巴尔多以教皇使节的身份给他们出具一纸公文说明：因为克莱芒特教皇去世后暂时没有选出新的继位者，所以他们没能完成使命。
根据马可的记载，他们向泰奥巴尔多表示：阁下，这么长时间都没能选出新的教皇，我们不能再耽搁了，得尽快返回蒙古帝国。
我们会向忽必烈汗转达您对他的问候，同时我们还想请您以教皇使节的身份出具一封公文解释一下事情的原委。
从兄弟俩的这番话可以看出，他们很擅长与那些具有影响力的人物进行协商，最终他们得到了想要的答复：既然你们想回去见大汗，我对此表示高兴。
泰奥巴尔多是否把忽必烈称作大汗值得怀疑，但有一点是显而易见的，那就是他想通过波罗三人与蒙古帝国的统治者建立外交关系。
他答应一旦选出新的教皇，一定会设法通知忽必烈汗。
一切基本就绪后，波罗三人立刻动身前往亚美尼亚的莱亚苏斯港准备返回蒙古帝国，三年前波罗兄弟也是从这里踏上了回家之路。
虽然莱亚苏斯港面积狭小，但马可称：这里云集了来自威尼斯、波斯、热那亚和所有内陆地区的商人，为了方便做生意，商人们在这里兴建了很多货仓。
就在他们即将动身的时候，这里突然爆发了一场叛乱，马可说：为阻止敌人的围追堵截，成吉思汗的一个孙子命人在沙漠中开挖出很多战壕和地沟，导致多条主要道路被毁。
这次叛乱将波罗三人困在了莱亚苏斯。
就在他们无奈地等候平息叛乱的同时，一位罗马教廷的信使给他们带来一个惊人的消息：1271年9月1日，在经过有史以来最长的一次酝酿，枢机主教们终于选出了新的教皇，而新教皇不是别人，正是他们熟悉的泰奥巴尔多。
马可称：兄弟俩听到这个消息后高兴不已。
信使同时还带来新教皇的命令，让他们返回阿迦。
于是，在武装护卫下波罗三人重新回到了阿迦城。
这次去阿迦，波罗兄弟可谓收获颇丰，已身为基督教界最高领袖的泰奥巴尔多设宴款待了他们。
教皇还仔细考虑了忽必烈提出的心愿，认为这是在蒙古帝国尤其是在整个中原地区传播基督教的一次很好的机会，于是教皇同意派出两位修士与波罗三人同行。
按照马可的叙述：这两位修士是整个主教区最为博学和高尚的人。
他们享有很多特权，而且在教皇的权利范围之内，这两位修士可以不受限制做很多事，甚至可以像教皇一样任免主教和牧师。
教皇还让两位修士带上送给蒙古大汗的水晶、珠宝及其他礼物。
总之，朋友荣升为教皇并因此给他们带来这么多好处对波罗兄弟来说，的确是一件幸事。
于是他们满怀憧憬地踏上了东去的征途。
征途总有波折。
在途经亚美尼亚时，波罗三人触犯了当地的首领比巴拉苏丹。
比巴拉扬言要监禁三人，两位修士出于安全考虑拒绝再与他们同行，但是波罗三人已经为此事历经千辛万苦并耗费了大量时间，所以他们是绝不会轻易放弃的。
三人一致认为，可以和部落首领通过谈判来解决问题，当然最管用的还是用珠宝贿赂他们。
最终，虽然没有了教皇侍卫的陪同，尼科洛、马费奥和马可仍然坚持东进。
1272年3月27日，泰奥巴尔多在罗马被正式封为格利哥里十世。
而此时，为了教廷、为了蒙古帝国和东西方微妙复杂的关系，波罗一行三人正在遥遥无期、风险莫测的旅途当中艰难跋涉。
在基督教徒看来，他们三人在各种极为不利的条件下坚持去东方，无异于踏上了一条不归路。
成功的机会微乎其微，如果真能生还绝对是个奇迹。
然而，波罗三人的看法却截然相反。
他们深信东方遍地是贸易机会，并且只要做事稳妥就一定会有收益。
他们以商人自居，而不是把自己当作基督教的卫道士或者使者。
在他们看来，贸易可以冲破一切文化差异和冲突的阻碍，而他们正好可以利用这次机会将自己的想法通过实践来进行检验。
如果想法是正确的，那么他们将荣归故里，声名显赫。
如果想法错误，他们将从此隐姓埋名，不为人知。