The present article relates the historical circumstances which gave way to the firts contact between the Byzantine Empire and al-Andalus. A very complex situation afflicted Byzance, under pressure on all sides by the Islamic expansion, which advanced over territories priorly belonging to Persia, or to oriental Christianity. Morover, the internal situation of the Empire was critical, due to the disputes sustained between the iconoclasts and their oponents; this made Basileus Theophilus incapable to detain the islamic advance. At this point, he asked for the help of the emir of al-Andalus, Abd al – Rahman II, requesting that he take charge of a group of exiliates who had occupied the territories of Crete – strategic position of the Byzantine Empire. The author analizes the characteristics and conditions of the diplomatic relations, by analizing the answer given by the emir. This reply is the historical source which allows the reconstruction of the complete historical sceneru, including the petition of the Byzantine Basileus.