Muslim maritime activity along medieval Italy’s shores is nearly always described by modern scholars as piracy, and the small communities of Muslims living in early medieval southern Italy and outside of Rome as “pirate’s nests.” Such labels allow scholars to ignore the possibility of a formative presence of Muslim individuals and communities in early European territories or maritime spaces. What if, instead of dismissing these Muslims as nothing more than bothersome but temporary raiders and pirates, scholars took seriously the presence of Muslim people in early medieval Europe and in the waters off European shores? How would the story of early medieval Europe broadly, and medieval Italy specifically, change if we see them as places where Muslims lived and worked as legitimate neighbors to the Greek and Latin Christians, Jews, and others who populated the region? This paper offers a more nuanced perspective on the deep interconnections between Muslims and others in southern Italy and in the waters of the Tyrrhenian Sea. These interconnections involved both violent and peaceful encounters that defy a clear binary between licit and illicit activity. It will focus on two sets of medieval sources: Arabic chronicles from North Africa that describe Muslim naval activity near Sicily and southern Italy, most of which were written centuries after the time described; and contemporary Italo-Greek texts that portray interpersonal encounters between Muslims and Christians on both land and sea. Such interpersonal encounters blur the distinctions between violent raiding and peaceful encounters. Violence, raiding, and destruction were certainly part of the story of Muslim presence in early Italy; but so too were more mundane interactions such as trade, interpersonal dialogue, sharing food together, and diplomatic exchange