Aware of medieval Crusades and recent conflicts between the West and the Muslim world, people today often imagine the early history of European-Muslim interaction as one characterized by harsh words and harsher violence. In fact, war and blood are only part of the story of the contact between Christendom and the Muslim world, a story that involves constant interactions between thriving and evolving cultures that embraced mutual benefit as readily as conflict. Bustling trade, philosophical exchanges, ethnic and social diffusion, artistic collaboration and inspiration, alliances and diplomacy, and invective and war were all part of the rich and fluid relationship between these joint heirs of the Roman Mediterranean. We examine the first millennium of European-Muslim encounters to gain an appreciation of these complex interrelationships.