Fatima perustettiin huhtikuussa 1998 neljän ex.Le'Cheri-jäsenen toimesta: Hitomi (laulu), Mizuha (kitara), Lay (basso) ja Daisuke (rummut).
Jo joulukuussa oli ensimmäinen maxi-single Downer kasassa. Ensimmäinen esiintyminen oli pian Tokion CYBER clubilla. Kesäkuussa 1999, myöskin CYBERilla soitetun keikan jälkeen, Daisuke lopetti (liittyäkseen Kagerouhon vokalistina kolmea kuukautta myöhemmin). Fatima siis jäi ilman rumpalia ja aktiviteetit jäädytettiin miltei vuodeksi.
6. elokuuta 2000 Fatima palasi uudenlaisena. Hitomi vaihtoi nimensä Sanakaksi ja Naosta oli tullut uusi rumpali. Sen lisäksi bändillä oli nyt kakkoskitaristi, Zen. Elokuun 9. päivä oli entistä ehomman Fatiman ensimmäinen live lähes vuoteen.
Syyskuussa, ennen seuraavaa sinkkua, Zen jätti bändin ja mielenkiintoista kyllä, Daisuken tavoin hänestäkin tuli vokalisti uuteen bändiin nimeltä Vanilla. Fatima hankki uuden kitaristin, joka esiintyy nimellä 4ge ("Shige").
2002 ilmestyi seuraava single, Mr:I-44. Fatima esiintyi paljon ja bändi näkyi myös lehdissä. Lokakuun 27. vaihtui jälleen jäsen ja Naon lähdön jälkeen rumpaliksi löytyi Towa.
Vuosi ehti jälleen vierähtää ennen kolmatta singleä. Noble King Snake saatiin ulos maaliskuussa 2003.
Samoihin aikoihin Fatima keikkaili Vanillan kanssa ja toukokuussa ilmestyi näiden kahden bändin yhteinen maxi-single.
Marraskuun 14. 2003, vain päiviä ennen tärkeitä konsertteja, Sanaka sairastui vakavaan keuhkosairauteen. Pahinta pelättiin, mutta onneksi hänen kuntonsa nousi nopeasti ja jo saman vuoden jouluksi Sanaka jaksoi olla mukana Fatiman erityisellä joulukeikalla.
Seuraavan maxi-singlen, Shizumu Taionin, aika oli maaliskuussa 2004. Näin harva julkaisuväli (6 vuoden aikana 5 singleä) on harvinainen niinkin hyvin pärjäävälle yhtyeelle. He kiertävät usein soittamassa musiikkiaan ja lehdet tekevät juttua. Suuria suunnitelmia lähitulevaisuutta ajatellen ei tuntunut olevan, mutta ei myöskään pienintäkään aikomusta lopettaa.
Fatiman jäsenillä oli aina myös muita puuhasteluja: Lay osallistui Bluck Tlick-projektiin, jossa oli mukana myös Tatsurou (MUCC), Aie (Deadman), Yuu (Merry) ja Tsuyoshi (Karimero). Myös Mizuhalla oli samankaltainen sessioprojekti meneillään. Fatimalla on myöskin oma, puolitosissaan otettava "alter ego" - Downer - jossa soittavat samat jäsenet eri nimillä.
Vuoden 2004 lopussa Fatima julkaisi kaksi singleä lisää: toinen oli maxi-single Kasenai ame/muchi na inochi e ja toinen "kolikon CD", vain 500 jeniä maksanut Tsumugi Ito, jota myytiin eri keikoilla erilaisin kansin varustettuna.
Tammikuun 1. päivä 2005 vaihtoi Sanaka jälleen nimensä: nyt hän oli Kanoma. Fatima julkaisi ensimmäisen ja samalla myöskin viimeisen minialbuminsa 27. huhtikuuta 2005. Syntymäpäiväkeikallaan Kanoma tapansa mukaan esitti ilmoituksen. Tällä kertaa se oli ikävä, sillä Fatiman kerrottiin lopettavan. Viimeinen kiertue, 「to Exit」, järjestettiin kesäkuussa ja sen päätöskonsertti 26. kesäkuuta Shibuya O-Eastilla. Tuosta keikasta julkaistiin joulukuussa muhkea DVD, sisältäen 24 laulua sekä ekstroja - uskolliset fanit eittämättä olivat ansainneet bändiltä muistoksi oman videojulkaisun.
Towa ja Kanoma ovat pysytelleet näkyvillä osallistuen erinäisiin visual rock -tapahtumiin ja bändisessioihin. Eräässä projektissa he ovat soittaneet Disney-elokuvien tunnussäveliä.
