多次交谈之后，尼科洛和马费奥取得了大汗的信任，他们之间的关系也日渐融洽。
后来，大汗决定让兄弟俩做他的西方使臣，承担出使教皇的任务。
大汗很善言辞，委婉地向波罗兄弟提出了自己的计划，用马可的话说就是，大汗恳请兄弟俩能陪同他的一位叫科加达尔的宠臣前去面见教皇。
一开始兄弟俩还有些犹豫不定，他们告诉大汗：我们离开欧洲已经很长时间了，沿途的情况肯定发生了变化，所以我们也不清楚途中会发生什么事或者该做些什么。
我们恐怕会辜负陛下的一番心意。
不过最终他们还是同意赴命，当然也很可能是被迫同意的。
忽必烈汗在给教皇的官文中提出，希望能派一百名学识渊博，熟悉七艺，能言善辩且熟悉基督教教义的智者来教化他的子民。
这些人要在蒙古人中宣传基督教，也就是说，要能让他和蒙古帝国的偶像崇拜者们，以及皈依了其他宗教的信众明白，他们现在的宗教信仰是错误的，而且供奉在家中的神灵都是邪恶的。
教皇派来的使者要让所有的人都相信，基督教比其他宗教信仰好得多。
这番话在深信忽必烈就是恶魔之子的教皇看来，绝对是不可思议的，但事实上，这倒也符合忽必烈喜欢探究和尝试新事物的性格特点。
如果教皇和他的使者们真能按照忽必烈所希望的那样去做的话，那么大汗和所有蒙古达官显贵就都有可能成为基督教徒，不过这并不意味着他们会弃绝其他宗教信仰。
忽必烈还希望他们带回一些耶路撒冷耶稣墓冢上方点灯的灯油，他认为耶稣是能给人类带来福祉的神之一，所以他对耶稣非常崇敬。
不过，他只是想让耶稣成为蒙古万神殿中众多神灵之一，而不能取代其他的神灵。
忽必烈的这一想法和教皇的期望之间有很大出入，而且他的想法根本不会得到罗马教廷的认可。
但此时波罗兄弟只想着个人安危，哪里还有心思去和忽必烈理论神学，为了能安全返回威尼斯，他们再三向忽必烈保证一定会按他的要求完成使命，带回一百名智者并且从圣墓取回灯油。
不知兄弟俩是否真的认真考虑过自己有无能力去完成所承诺的每一项任务，但至少在当时的条件下，仅带一百名智者原路返回蒙古这一项就根本无法实现，而从圣墓中取回据说能医治身心疾患的灯油则可另当别论，因为他们早就知道亚美尼亚的教士就靠出售圣灯油而大肆敛财，所以波罗兄弟俩才认为他们完全可以出高价买回灯油。
为了确保两位威尼斯客人的人身安全，忽必烈汗还按照蒙古习俗为他们配发了一块刻有他的印章和签名的金牌。
这块金牌是蒙古皇室的通行牌，证明尼科洛、马费奥及科加达尔三人是忽必烈汗的钦差，沿途所有的官府都必须像见到了大汗本人一样，给他们提供住宿、马匹和护送。
任何人不得违抗，否则便有犯上之嫌。
一行人离开大都二十天后，科加达尔便因身染重病而被迫放弃。
在随后的行程中波罗兄弟仰仗着大汗所赐的金牌一路畅通无阻。
不久，兄弟俩顺利到达位于小亚细亚幼发拉底河西岸的一个小港口城市莱亚苏斯，并在这里登船开始了他们最危险的一段旅程。
在陆地上时，他们只是担心会遭遇敌人，但上了船后，他们内心时时充满了恐惧，因为在当时，只有勇猛无畏或者走投无路以及头脑发热的人才会选择水路，把自己的生命托付给凶险莫测的海浪。