alternatehistory.com

I gather from the Wiki that this is something of a cliché here, but anyway, let´s take a look at it.

Let´s say that, either just the Yongle Emperor or all the early Ming emperors, Hongwu and Jianwen as well as Yongle, have this deep-seated fascination with and desire to find Mount Penglai, location of the fabled Eight Immortals.
Now, clearly the purported location of the island holding Mount Penglai in the eastern Bohai Sea is not true, which would relatively quickly be ascertained. This must (to the Ming emperors) mean, however, that the Mount Penglai is on a much more distant island, so in 1405, the Yongle Emperor commission Zheng He to search for them.

Zheng He´s first two voyages thoroughly explore more or less known islands east of China - Taiwan, the Pescadores, Jeju, the Ryukyus, Japan -, but succeed only in ascertaining that Mount Penglai is not located there.
Still, the Yongle Emperor is certain that Mount Penglai is to be found on an island somewhere east of mainland China, so on his third voyage, Zheng He reaches the Sea of Okhotsk and explores Sakhalin, the Kuriles and Kamchatka, which is initially thought to be an island.
On the fourth and fifth voyages, fleets commanded by Zheng He reach ever further East and North, although the arctic climate prevents them from penetrating far beyond Bering Strait. They ascertain that none of islands in and around the Bering Strait are the place they seek, and that there is a major landmass east of the Bering Sea, probably too large to be considered an island.

Zheng He´s sixth voyage (starting in 1421), then, explores the southern coast of Alaska and then further East and South until they reach the coast of California, where a terrible storm wrecks part of Zheng He´s fleet; the survivors seek refuge in San Francisco Bay. Determining that his ships have sustained too much damage, and too many supplies are lost, for his fleet to return to China in their current state, he establishes a base in the bay. Establishing the facilities needed to repair the fleet´s large ships and gathering the repair materials and the supplies for the return voyage takes two years, during which Zheng He leads some of the smaller ships to further explore the coast of the new continent, eventually making contact with the Mexica and Maya in 1424. Although the expedition did not carry notable amounts of trade goods, enough of the things they brought are desirables to the locals to procure samples of Mesoamerican product - not much compared to the costs of the expedition, but enough to prove that there is both a market for Chinese goods in the lands beyond the eastern oceans and a source of new and desirable commodities.
By the time Zheng He and his much reduced fleet finally return from his sixth voyage in 1426, both the Yongle Emperor and his son, the Hongxi Emperor, have died. While the now-reigning Xuande Emperor does not have nearly the same enthusiasm for costly overseas expeditions to locate Mount Penglai as his grandfather, tales of the Mesoamerican civilisations - and the tangible proof of Mesoamerican trade goods - convince him to finance another expedition to be led by Zheng He, with the proviso that any expeditions beyond this one must be financed from the trading profits of previous expeditions.

Zheng He´s seventh voyage (starting 1429) travels straight across the Pacific from the eastern coast of Japan to the San Francisco Bay anchorage, a region Zheng He proceeds to name "Xinjiang", "New Territory", to establish a permanent base there - at least as permanent as the series of future trading and exploratory voyages. This voyage´s focus is clearly on trade with the Mesoamericans, although the Chinese will also explore the Xinjiang region for some distance inland - to scout for potential enemies, if nothing else.
The expedition trades mainly with the Zapotec, Mixtec and southern Mayan people on the coast, although Chinese emissaries also travel throughout central Mexico, where the Triple Alliance (the "Aztec Empire") completed their overthrow of the Tepanec, overland to Yucatan, and some distance further South-East along the coast, about as far as OTL El Salvador.
Financially, the expedition is a great success, paying not only for itself but also for several further fleets to China´s new trading partners. Zheng He, however, is not to live long enough to know that; he dies in 1434, during the return voyage to China.

********

All right, that´s the start. I am not entirely sure yet where to take this, but would appreciate feedback.
Top