Une perturbation tropicale s'est formée le 29 février 2004 dans l'océan Indien au sud de Diego Garcia. Il fut pris en charge par le Centre météorologique régional spécialisé (CMRS) de La Réunion, côté civil, et par le Joint Typhoon Warning Center (JTWC), au militaire, le 1 mars. Le système se dirigeait ouest-nord-ouest à une bonne vitesse et évolua rapidement en tempête tropicale, nommée 16S par le JTWC et Gafilo par la Station Meteorologique de Ile Maurice, puis en cyclone tropical (le 4 mars, générant des vents de 120 km/h et des rafales à 170 km/h. Le lendemain, Gafilo atteint le stade de cyclone tropical très intense (équivalent à la catégorie 5 de l'échelle de Saffir-Simpson), avec en son centre une pression record de 895 hPa. Gafilo génère alors des vents moyens de 230 km/h avec des rafales à 326 km/h. Il touche terre après minuit la nuit du 6 ou 7 mars sur l'île de Madagascar, près de la ville d'Antalaha.
Gafilo traversa la partie nord de l'île puis continua son trajet sur mer dans le canal du Mozambique, il avait alors perdu beaucoup de son intensité et était redevenu de catégorie 1. Le 9 mars, il fit demi-tour et retraversa le Sud de Madagascar avec la force d'une tempête tropicale. Il s'évacua lentement vers le sud-est jusqu'à l'océan puis continua à faiblir, rencontrant des conditions défavorables de cisaillement de vents en altitude et de température de surface de la mer.
