|The much-disputed Crimean Peninsula|
Invasions took place throughout the Classical and Medieval Eras. A group now referred to as Crimean Tatars (descendants of the Mongols of Genghis Khan fame) thrived there in the Middle Ages. Despite their numbers, the Tatars did not always control the territory. Venice created several settlements on the coast in order to control trade on the Black Sea; these were taken over by Genoa in the 13th century and controlled by them for the next two centuries.
...and here's an interesting tie-in to one of the best-known events of the Middle Ages. The first appearance of the Black Death in medieval Europe came on twelve Genoese ships coming from the east in October 1347 and landing in Sicily. It is entirely possible that Crimean ports were the source of the Plague.
In the era of Tamerlane, the Crimean Tatars finally asserted control over most of the area—except the Genoese towns—establishing the Crimean Khanate in 1441 under the rule of a descendant of Genghis Khan. The Genoese towns were finally captured, but not by the Tatars. The Ottoman Empire conquered the Genoese towns, then took the current Crimean Khan captive. He was released after the Tatars recognized the sovereignty of the Ottomans.
In the late 1700s, a treaty between the warring Russian and Ottoman Empires left the Crimean Peninsula in the hands of Russia, one step closer to the present controversy.