This paper sets out to disentangle what is discernible from the historical record and the evidence from legendary accounts of the spread of Islam by conquest. It argues that rather than by the sword, Islam came to Spain through the development and succession of ideas. The paper further deconstructs the theory of Islamic governance, attributing forms of rule not to Islamic teachings but to prevailing power structures and struggles. It is contended that what is known of specific incidents reaches us through the narration of the incident, rather than by its physical existence. If a serious event takes place, it reaches us through a serious Hadith (like the Prophet's Hadith), but if the incident is not very significant or did not take place at all – but an authority wants it to have happened – it reaches us as a legend. The legend starts where history ends, and takes its place to complete the story's events. History depicts and legend narrates.