About 1200 the Genghis Khan, Great Khan (emperor) of the Mongol Empire, installed an empire-wide messenger and postal station system named Örtöö within the Mongol Empire. During the Yuan Dynasty under Kublai Khan, a grandson of Genghis Khan, this system also covered the territory of China. Postal stations were used not only for the transmission and delivery of official mail, but were also available for traveling officials, military men, and foreign dignitaries. These stations aided and facilitated the transport of foreign and domestic tribute, and trade in general.
By the end of Kublai Khan's rule there were more than 1,400 postal stations in China alone, which in turn had at their disposal about 50,000 horses, 1,400 oxen, 6,700 mules, 400 carts, 6,000 boats, over 200 dogs and 1,150 sheep. The postal stations were 15 to 40 miles apart, and had reliable attendants. Couriers reaching postal stations would be provided food, shelter and spare horses. It was estimated that couriers could travel 20-30 miles per day. Foreign observers, such as Marco Polo attested to the efficiency of this early postal system.
These statistics were taken from a Wikipedia article. An Excerpt from The Book of Ser Marco Polo: The Venetian Concerning Kingdoms and Marvels of the East. Volume 1, translated and edited by Colonel Sir Henry Yule (London: John Murray, 1903) available online at http://afe.easia.columbia.edu/mongols/figures/ser_xxvi.pdf contains additional and different details.