Expanded a bit from an earlier answer of mine, on "Did Europe ever have a ruler of African descent?":

In 711 CE, an Umayyad army conquered a large amount of the Iberian peninsula (modern Spain and Portugal), leaving a narrow band at the top, and pushed up a little bit into France. From 756, too, Muslim armies began to push onto Sicily and would eventually conquer the whole island. The initial invaders would most likely have come from the Near East. We can trace a lot of anti-Berber (North African) sentiment, but that doesn't necessarily mean there were not Berbers in those early armies. In Iberia, there was fairly wide conversion of Visigoth Christians to Islam over time, and "intermarriage" wasn't even really inter-marriage anymore. However, Normans (late of France) conquered Sicily again in the 11th century, and from sometime in the same century up through 1492, Christians began to push down from northern Iberia and eventually held the whole peninsula. This is probably the span of time you're referring to, and as you can see, the details are a little off.

But let's take a closer look--what do we know about African rulers in and of places in Europe?

By the middle of the 11th century, the powerful Umayyad Caliphate of Cordoba had splintered under the weight of assassinations, coups d'etat, civil war--the usual. And the taifas (independent kingdoms) that arose in its wake faced a new problem: the newly aggressive, proto-crusading Christians to its north. They called for aid, and the powerful Almoravid dynasty answered--the dynasty based in modern-day Morocco. Yusuf ibn Tashfin came storming across the Strait of Gibraltar and defeated the Christians handily.

And then he proceeded to defeat the taifas handily, too, adding southern Iberia to the Almoravid empire. Yusuf personally kept his court in Marrakesh, so you wouldn't quite say there was an African king in Europe. However, he did install various African Almoravids as governors and other delegated ruling positions in Iberia.

The Almoravids were Berbers. "Race" as such didn't really exist at the time and it's important not to essentialize skin color as "African-ness," but it's interesting to see that from the Christian European perspective at least, skin color was not the defining characteristic of this group. The "Book of Games" from the 13th century presents us with pale-skinned Muslim women, for example, and almost sub-Saharan African-looking Almoravid men. (It's not a question of gender norms--there are some lighter-skinned male scholars elsewhere in the manuscript).

The case of Alessandro de Medici that you refer to, OP, is parallel--John Brackett has argued based primarily on artistic depictions that the duke's mother was a Berber slave in Italy. (And, I have to say, in the book itself, the black-and-white reproduction of that image makes his skin seem much darker, which strikes me as a very modern, politicized choice. I would be very curious to see this painting in person.)

The Almohad Caliphate, also Berber, replaced the Almoravids in the late twelfth century and ruled Islamic Iberia for a short time. But they maintained their capital/central court in Marrakesh as well.

As far as definitely sub-Saharan African? There is a fair amount of contact starting in the fifteenth century, with the Portuguese increasingly involved in the Kongo, traveling to the Swahili coast, and diplomatic connections forged between the Kingdom of Ethiopia and the Church in Rome. There was even an Ethiopian Orthodox church in the holy city! For a brief time, it almost seemed like European and Christian African kingdoms could merge and work in the same political-social system as within Europe!

In 1428, ambassadors between King Alfonso V of Aragon and Emperor Ishaq of Ethiopia actually worked to set up a double marriage alliance: Ishaq would marry the king's sister, and the Spanish prince would wed an Ethiopian princess. Nothing came of this, however. In the sixteenth century, the Ethiopians made a half-hearted attempt to revive the hope of a ruling marriage alliance, but they never got around to proposing specifics and the Portuguese weren't the least bit interested, anyway. By that point, the trans-Atlantic slave trade was picking up and Europeans were starting to theorize about patterns that had been developing silently with the growing presence of African slaves in European courts. Literature and legal sources began to delineate hierarchies of skin color, and the (white, Roman) Church pondered questions of skin color, conversion, and the ethics of enslavement.

~~

Further Reading: If you have access to an academic library, I highly recommend the anthology of essays Black Africans in Renaissance Europe, ed. T.F. Earle and K.J.P. Lowe (2005). It includes the Brackett essay I mentioned above. While the overwhelming focus on Iberia and Italy is less than ideal, that has the advantage of bringing the highlights of the Spanish and Italian-language historiography on the topic of Africans in pre/early modern Europe into English.