Вице-король Неаполя формировал роту, чтобы передать ее в командование своему сыну. Несмотря на то, что он знал, почему Алонсо и его приятели бежали из Палермо, он принял беглецов и разрешил им поступить на службу, которая, однако, оказалась недолгой. После очередной драки, закончившейся убийством, двое компаньонов Алонсо были повешены. Сам он бежал к одному мальтийскому рыцарю, который его спрятал, а потом тайно посадил на корабль, отправлявшийся на остров. Мальта была не только христианским аванпостом в борьбе против турок, но также и опорным пунктом испанского флота, действовавшего в восточной части Средиземного моря, и рыцарям нужны были матросы, чтобы формировать экипажи для своих галер. Так Контрерас поступил на службу к гроссмейстеру Мальтийского ордена, французу Алофу де Виньякуру, и принял участие в нескольких морских битвах, описания которых представляют собой живые свидетельства о том, чем была в те времена морская война: