In 2000 nam Khaldi een eerste keer deel aan de Olympische Spelen van Sydney. Hij werd in de eerste ronde van de 1.500 m al uitgeschakeld met een tijd van 3.41,16. In 2002 haalde hij op de Afrikaanse kampioenschappen tweemaal de finale: op de 1.500 m werd hij zevende in een tijd van 3.43,46 en op de 5.000 m werd hij negende in 13.52,33.
Op de Algerijnse kampioenschappen in 2004 boekt hij zijn eerste titel door de 5.000 m te winnen in 13.51,21. Op de Olympische Spelen van Athene later dat jaar kwam Khaldi net als vier jaar eerder uit op de 1.500 m. Wederom sneuvelde hij in de voorrondes ditmaal met een tijd van 3.42,47. Na deze Spelen liep hij geen internationale wedstrijden meer.