It seems like everyone has been to the castle at Bilhorod-Dnistrovskyi. Built by the Byzantines but part of the Kievan Rus, it was controlled briefly by Genoans and Hungarians, attacked by the Turks and defended by Moldovans. In the late 15th-century, with Prince Stephen of Moldova busy fighting off the Poles, the Turks tricked its defenders into surrendering before slaughtering everyone inside. It remained in their hands for three hundred years.
From Russia the castle ping-ponged to Romania, which was given the city as part of the peace negotiations that ended WWI. Stalin recaptured it in 1940 but held out for less than a year before the Romanians came back. The Soviets swept through in 1944 and from then on it's been part of Ukraine.
Nowadays it's anyone's for 40p - and they even let you climb on the walls.