En 1304, Andrea Morisco se met au service de l'empereur byzantin Andronic II Paléologue qui le fait bestiariou[1]. En effet, Andronic a supprimé la marine byzantine pour alléger les finances très réduites de l'Empire byzantin. Cela l'oblige à faire appel aux Italiens pour assurer la défense maritime de l'empire. Andrea Morisco est de ceux-là et avec deux navires, il réussit à infliger des pertes aux Vénitiens et aux Turcs[2]. Il est récompensé par l'empereur mais dès 1305, il s'attaque à l'île de Tenedos dont il expulse les habitants et prend le contrôle. Cette attitude montre les limites de la solution d'Andronic II à sa décision de compter sur l'aide extérieure pour remplacer la défunte marine byzantine. Toutefois, lors de l'épisode de la compagnie catalane qui voit l'installation de mercenaires catalans dans la péninsule de Gallipoli de 1305 au début des années 1310, Andrea Morisco se met de nouveau au service de l'empire en patrouillant dans l'Hellespont pour empêcher les Turcs de grossir les troupes catalanes qui ont quitté le service de l'empereur pour constituer une forme de principauté catalane indépendante. Andrea Morisco reçoit le titre d'amiral en récompense mais il est ensuite fait prisonnier et ne peut plus empêcher les Turcs de rejoindre l'Europe[3].
