When the former Seljuk Sultan Kaykaus II was arrested in the Byzantine Empire, his younger brother Kayqubad II appealed to Berke. With the assistance of the Kingdom of Bulgaria (Berke's vassal), Nogai invaded the Empire in 1264. By the next year, the Mongol-Bulgarian army was within reach of Constantinople. Nogai forced Michael VIII Palaiologos to release Kaykaus and pay tribute to the Horde. Berke gave Kaykaus Crimea as an appanage and had him marry a Mongol woman. Hulagu died in February 1265 and Berke followed the next year while on campaign in Tiflis, causing his troops to retreat.