The recipient of a classical education at his father's palace in Anhialo, Andronikos learned to speak and write in Greek, Italian, German, New Latin, and Ottoman Turkish. During his son's early years, Şeytanoğlu pursued a political alliance with the Rhali merchants, marrying Andronikos' elder sister to one member of that family, setting her a dowry at 40,000 ducats. Another sister reinforced the family's genealogical claims by marrying Anthony Kantakouzenos, a merchant from the Crimean Khanate. In 1576, Şeytanoğlu oversaw the marriage between Andronikos and Irene, daughter of the merchant Jacob Rhali from Edirne. The lavish wedding itself may have played a part in Şeytanoğlu's downfall, contributing to his arrest for tax evasion, during which he was shown to be involved in an anti-Ottoman intrigue. One theory, advanced by scholar Matei Cazacu, is that Sultan Murad III had discovered Kantakouzenos' sponsorship of Ioan Potcoavă, who wanted to take Moldavia out of the Ottomans' orbit. Andronikos was also imprisoned, then, in March 1578, was forced to watch as his father was hanged at Anhialo. He escaped more serious punishment by taking flight across the Black Sea to Istanbul, where he asked and obtained protection from Şeytanoğlu's friend Sokollu Mehmed Pasha, the Grand Vizier. He was detained as a galley slave for the Ottoman Navy, but Sokollu released him after some weeks of servitude, with Andronikos promising to liquidate his father's debts. The persecutions also fell on the "Palaiologoi" branch of the Kantakouzenos, with Constantine fleeing for safety to the Crimean Khanate. From about 1585, Andronikos rebuilt his father's business ventures and resumed contacts with traders from the Republic of Venice and from all over Lombardy; like Iane, he also became involved in the lucrative business of princely appointments in Wallachia. In various records, he is credited with having obtained in 1591–1592 the Wallachian throne for the Moldavian Stephen the Deaf. He himself was Prince Stephen's "Vistier" from June 1, 1591 to May 28, 1592, and again in July 1592.