Souad Aït Salem boekte haar eerste grote succes in 2000 met het winnen van 10.000 m op de Afrikaanse kampioenschappen in haar eigen land. In haar Algiers versloeg ze met een tijd van 34.02,28 de EthiopischeGenet Teka (zilver; 34.05,18) en de MarokkaanseBouchra Chaabi (brons; 34.08,79). In 2002 werd ze vijfde op de 10.000 m bij de Afrikaanse kampioenschappen. Op de wereldkampioenschappen atletiek 2003 in Parijs en de Olympische Spelen van 2004 in Athene werd ze in de halve finale van de 5000 m uitgeschakeld.
Haar doorbraak op de weg maakte ze in 2006. Op haar marathondebuut in Griekse stad Thessaloniki won ze gelijk de wedstrijd in 2:28.22 en op het WK 20 km in het HongaarseDebrecen werd ze negende in een nationaal record van 1:06.11. In het jaar erop verging het haar nog beter door de marathon van Rome te winnen in een nieuw parcours-record en nationaal record van 2:25.08. Op de Olympische Spelen van 2008 in Peking werd ze negende in 2:28.29.