In 1252, Niccolò and Maffeo left Venice for Constantinople, where they resided for several years. The two brothers lived in the Venetian quarter of Constantinople, where they enjoyed political chances and tax relief because of their country's role in establishing the Latin Empire in the Fourth Crusade of 1204. But the family judged the political situation of the city precarious, so they decided to transfer their business northeast to Soldaia, a city in Crimea, and left Constantinople in 1259. Their decision proved wise. Constantinople was recaptured in 1261 by Michael Palaeologus, the ruler of the Empire of Nicaea, who promptly burned the Venetian quarter. Captured Venetian citizens were blinded, while many of those who managed to escape perished aboard overloaded refugee ships fleeing to other Venetian colonies in the Aegean Sea.

Niccolò and Maffeo Polo leaving Constantinople for the east, in 1259:

As their new home on the north rim of the Black Sea, Soldaia had been frequented by Venetian traders since the 12th century. The Mongol army sacked it in 1223, but the city had never been definitively conquered until 1239, when it became a part of the newly formed Mongol state known as the Golden Horde. Searching for better profits, the Polos continued their journey to Sarai, where the court of Berke Khan, the ruler of the Golden Horde, was located. At that time, the city of Sarai — already visited by William of Rubruck a few years earlier — was no more than a huge encampment, and the Polos stayed for about a year. Finally, they decided to avoid Crimea, because of a civil war between Berke and his cousin Hulagu or perhaps because of the bad relationship between Berke Khan and the Byzantine Empire. Instead, they moved further east to Bukhara, in modern day Uzbekistan, where the family lived and traded for three years.

Nicolò and Maffeo in Bukhara, where they stayed for three years. They were invited by an envoy of Hulagu (right) to travel east to visit the Great Khan Kubilai: