The events comprising the early Arab-Muslim expansion into Byzantine Syria and Sasanian Iraq became with time the foundational myths of Islamic collective memory. The texts that comprise the Futuh literature record in detail the battles that led to the early and sudden spread of Islam throughout the Near East. However, by reading between the lines, I contend in my paper that we can reveal important clues regarding the historicity of the battles themselves, as well as the nature of the society that produced these texts. More than simple history or even didactic lessons, I argue that we should read these chronicles not as historical recordings but as literary narratives that conveyed a story about how early Muslims saw themselves, remembered their past, and understood the larger rôle of Islam in human history. The conquests of Syria and Iraq both included one minor defeat—the Battles of Mu'tah and the Bridge, respectively—and one major victory—the Battles of al-Yarmuk and al-Qadisiyyah, respectively. I explore further the literary construction of Islamic historiography by looking specifically at the dynamic between these four battles, which calls for critical and careful scrutiny. Both of the victories, at al-Yarmuk and at al-Qadisiyyah, respectively, would quickly become celebrated events in the annals of Islamic history. However, a number of suspicious topoi, exaggerated numbers (of army sizes and casualties), and a remarkable overlap in the cast of protagonists and antagonists raise questions about the veracity of the details of these battles. Furthermore, by juxtaposing the reports of the two victories against those of the two defeats, a number of peculiar parallels emerge, suggesting that the accounts of the two victories sought intentionally to ‘respond’ to the previous defeats. In addition, a comparison of the victory on the Syrian front with that on the Iraqi front reveals traces of a geographic or tribal rivalry, in which the victors at al-Qadisiyyah and al-Yarmuk—or their descendants—competed with each other for the claim to a greater legacy of achievement. By removing layers of literary embellishment, not only do I highlight the quixotic nature of a search for an historical ‘kernel of truth’, but moreover, in doing so, I shed light on the construction of Islamic history, the generation of the paradigm of an Islamic conquest, and the general formation of the cultural memory of early Islamic society.