Madi veroverde zijn eerste Algerijnse titel in 2004. Nadien zou hij dat in 2006 en 2007 nog eens overdoen. In 2004 nam hij ook deel aan de Olympische Spelen van Athene. Met een tijd van 1.47,50 werd hij in de kwalificatieronde uitgeschakeld.
In 2007 liep Madi de 800 m in Heusden-Zolder in een persoonlijke recordtijd van 1.44,54. Hiermee was hij gelijk de tweede snelste Algerijn ooit. Alleen Djabir Saïd-Guerni liep nog sneller op deze afstand. Dat jaar kwalificeerde hij zich ook voor de wereldkampioenschappen in Osaka. Hier werd hij in de halve finale uitgeschakeld met een tijd van 1.45,59. Een jaar later deed Nabil Madi het op de Olympische Spelen in Peking beter. Ditmaal bereikte hij op de 800 m wel de finale, waarin hij op de zevende plaats eindigde in 1.45,96.
Algerije
