One wildly implausible idea ....
POD - 10th century - A kingdom emerges in West Africa, earlier and larger and more stable than OTL Ghana. Pagan at first, it later becomes predominantly Islamic. It expands to the north and comes to dominate most of northwest Africa. Seaborne trade develops between the northern and southern parts of this kingdom because ships can carry larger amounts of cargo than cross-desert caravans on land. By the 12th century it is discovered that ships can sail from OTL Sierra Leone or Senegal up to Morocco by steering well out to see and catching favorable winds. Canaries, Cape Verde Islands are discovered. By the time the west African Empire falls apart politically, its different regions remain joined by trade. In early 14th century a ship blown way off course to the west lands on the northeastern coast of OTL Brazil. Other ships explore north into the Caribbean.
By the early 15th century trade is being carried on between west and northwest Africa and Native Americans in Mesoamerica. With trade comes disease, waves of epidemics that sweep through a large part of the Americas and radically disrupt society. In the midst of this chaos, though, there is opportunity for some people in Mesoamerica. The strange men from beyond the eastern sea come in small numbers, and mainly to trade. They bring strange and powerful animals and weapons. Fortunes worth of gold and wilver and jade and feathers and cacao beans are exchanged for a few steel blades, a few pieces of metal armor, a few horses. Even larger fortunes are given to a few individuals to teach natives the secrets of some of these new items.
Near the fringes of a great inland lake in Mesoamerica, already a center of civilization for 2000 years, a relatively obscure tribe called the Mexica learn how to use the new steel and horses better than most. They go from being mercenaries of the most powerful tribes to being the most powerful tribe themselves. Large scale human sacrifices to Huitzilopochtli, their god of war, become their trademark. Personal bravery, discipline in battle and the use of the best weapons are all promoted by the priests of Huitzilopochtli and warrior societies.
As the Mexica push their domains outward toward the coast, the coastal people who did the most extensive trading with the merchants from across the sea become alarmed, and ask the foreigners for help. After a few years, a large expedition under the command of a veteran general from Morocco manages to assemble in the harbors of OTL Cuba and Panama. The core of this force consists of Muslims from northwest and west Africa, as well as Andalusia. There are also some Christians, mainly from the Mediterranean countries. They are supported by native auxiliaries. Marching into the lands of the Mexica, they smash the Mexican forces at first. Destroying temples of the devil-worshipers as they move along, they ultimately storm the Mexica’s capital of Tenochtitlan itself and devastate its main temple complex.
The Mexica, however, rallied under the leadership of a brilliant and charismatic member of the ruling family named Motecuzhoma. They besiege the invaders, and then force them to withdraw toward the coast. Most of the invaders from across the sea are killed, and those that are captured are sacrificed to the gods or used as slaves if they have special skills. The great temples in the capital and elsewhere are rebuilt larger and more magnificent than before. The leaders of the Mexica are determined to never be caught vulnerable by another invasion again. Using the best weapons and skills that they know, they will push the boundaries of their empire as far out as there are more lands to conquer. Someday, they vow, they will go beyond the great eastern sea, and conquer the invaders in their own countries.