The history of diverse relations between Byzantium, the heir to the Roman Empire, and the Arab-Islamic world went beyond war and conflict. While war did shape the initial contacts between the two sides, an important part of subsequent relations was characterized by official exchanges and coexistence. There was correspondence between kings and emirs and on-going contacts in border regions involving the ransom of prisoners, travel, and trade. Many studies have dealt with the Arabs and Byzantines respective perception of each other. This paper, however, will concentrate on the relatively neglected topic of language. This contribution can be viewed as research into the history of mentalities, which allows us to understand the linguistic mechanisms of Arabic involved in talking about the "other" and the effect of the imaginaire on that other. The paper seeks to address two questions: How did the Arabs represent the Byzantine "other" linguistically, and what words and terms did the Arabs use to talk about the Byzantines?