This chapter examines the relationship between the formative Muslim community and the Iranians residing in the Arabian peninsula, devoting particular attention to memory of the elusive Salman al-Farisi, the first Iranian convert to Islam. It analyzes portrayals of the Arabs' initial forays into Iraq during the reign of the first caliph, Abu Bakr. The chapter investigates the reports of the Muslims' encounters with the Sasanians occurring under 'Umar I b. al-Khattab. It presents the formulaic tropes and rhetorical themes contained within the embellished depictions of the embassies which the Arabs sent to the last Sasanian sovereign, Yazdagird III, and to his general, Rustam b. Farrukhzadh prior to the Battle of al-Qadisiyya. The chapter narrates the battle, followed by the conquest of Ctesiphon, the surrender of the Iranian magnate al-Hurmuzan to 'Umar, and the murder of Yazdagird. It analyses the Muslims' wars with the Romans, to assess the application of similar "Arab versus 'ajam" tropes from a comparative perspective.