Outline/rough idea for the beginning part. Using OTL ruler names for ease. They will be changed.
1090s: Old yet highly wealthy and the most powerful ruler in the West, Yusuf ibn Tashfin sponsors the colonization of the Canarias and the creation of a school for navigators. He did commission numerous naval bases and fleets in OTL.
Independent voyage from Lisbon carried to the Caribbean, never to be seen again and not noted until a almost a hundred years later. OTL legend of the Mugharrarin by al-Idrisi, except they don't return, and they settle in the island of Guadeloupe.
1106: Ali ibn Yusuf coronated.
1110s: Ali ibn Yusuf conquers, then loses Zaragoza. Disappointed, he looks to the wealthy final decades of his father's reign, visiting the school for navigators, who give him some ideas about areas to explore and some types of ships to build. Voyages go south to West Africa, and continue to go to the Canarias. One gets lost out West. An overland expedition through the Sahara, the largest yet, visits West Africa.
1120s: Crusader states, the Byzantine Empire, and a temporary Nubian dynasty of Egypt allied with the Crusaders isolate North African and Andalusian Islamic states from the East.
The voyage that got lost returns. They had faced Atlantic storms, crashing on the coast of Madeira, and had to live in the wilderness, all the while trying to rig a new vessel from the ruins of the three they lost. Upon returning, wanting some recourse for their hardship, they lie to Ali and say they found a vast Western land, hoping they will get sponsorship.
Ali believes this, and much to their dismay he asks that they join the voyage. They agree, then disappear never to be seen again, not wanting to be caught lying to the Sultan and not wanting to possibly go out on the ocean to die.
1130s: Ali begins to have troubles with the Masmuda. Caravel-like ship developed. Voyages continue, but not a transatlantic one as Ali realizes the men had attempted to lie.
Independent voyage managed by the Andalusians led by an Ahmad ibn Muhammad. They get carried into the Caribbean, settling on Hispaniola.
1137: Ali dies, succeeded by his son Tashfin. Tashfin sends five different voyages into the sea, eating away at the coffers. He is seen as disconnected from the world and somewhat crazy for the first few years of his rule, but then...
1141: Word returns of Bermuda, Barbados, and the Kongolese. Tashfin mounts an expedition of six ships and 800 men to the Caribbean, who find the already-settled Guadeloupe.
1144: Tashfin is killed by the Almohads in battle. He is succeeded by his infant son Ibrahim, who is assassinated in the same year.
1145: Ishaq bin Ali, brother of Tashfin, succeeds to the throne. After being defeated by Almohads, he and his supporters depart into the sea.
Plans were to relocate to Almeria and Valencia, but the fleet is intercepted. He then goes west and arrives in Cadiz, but rebels, Spanish marauders, or Almohads, he can't tell which, prevent him from setting up shop there. His crewmembers suggest going to the Canarias.
1146: Ishaq establishes his rule over the Canarias, and he sees the arrival of exiles after the Almohad conquest. The Almoravids persist in the Canarias.
1150s: The Almohads, having taken care of the more important Iberia and North Afirca, finally get around to conquering the Canarias. Ishaq escapes by sea, to the Caribbean.
Arriving in Guadeloupe, he establishes himself as the ruler there.
1160s: Abu Yaqub Yusuf of the Almohads begins to ravage Iberia, conquering city after city with vast African armies.
1170s: The Christians coalign against the Moorish threat, forming a Holy Coalition against the Almohads. The Battle of Castellón sees the death of the Almohad Sultan and a Christian victory.
1180s: Seeking revenge, Abu Yusuf Yaqub al-Mansur ends his regency, during which he was protected by powerful relatives, and invades the Christian kingdoms. Winning victory after victory, the Almohads reach a new height in their power.
During this age, philosophy, science, architecture, trade, and of course, navigation, flourish.
Capetown, the Antilles, Hispaniola, Cuba, and for the first time the mainland of South America, are all settled, conquered, or claimed.
Ghazis from Andalusia wreak havoc in the New World, usurping native tribes.
1190s: The golden age wasn't sustainable. In 1183 and 1184, the Marinids win some victories, taking swathes of North Africa. In 1189, a Christian coalition conquers Valencia.
1200s: The Almohads lose all but the region around Marrakech after the Christians win at Lisbon and the Marinids rise again
Moors are exiled by Christian victories, going to Morocco. Some of them go to the Canarias or the Caribbean.
1210s: The Battle of Jaén is won by Christians.
In the New World, Nasir ibn Muhammad unites Cuba.
1220s: The Marinids lead a charge north and reconquer various lands in Iberia. The Pope calls a Crusade, and Christians conquer Córdoba after restoring all the territories lost.
1230s: A deposed king of Mali relocates to Brazil. Christians conquer Sevilla.
1240s: Marinids rise again. Almohad puppet state is finally crushed, and the Marinids firmly hold Granada.
Marwan ibn Nasir, Emir of Cuba, conquers Mexico.