Madurajus gyvenamas bent nuo [[3 tūkstantmetis pr. m. e.|3 tūkstantmečio pr. m. e.]] Šaltiniuose minimas (kaip ''Methora'') nuo [[III a. pr. m. e.]], kuomet čia apsilankė graikų keliautojas [[Megastenas]]. Miestas taip pat minimas tamilų literatūroje, [[Plinijus Jaunesnysis|Plinijaus Jaunesniojo]], [[Ptolemėjus|Ptolemėjaus]], [[Strabonas|Strabono]] veikaluose. Nuo [[III a.]] miestą valdė [[Kalabharai]], vėliau – [[Pandijų dinastija]], kurios laikais Madurajus buvo valstybės sostine. Buvo užkariautas [[Čolų imperija|Čolų imperijos]], bet grįžo Pandijams. [[XIV a.]] Madurajus tapo [[Delio sultonatas|Delio sultonato]] dalimi, bet greitai atsiskyrė Madurajaus sultonatas, kuris užkariautas [[Vidžajanagaros imperija|Vidžajanagaros imperijos]]. Vėliau dėl pietų Indijos vyko kovos tarp musulmoniškų šiaurės dinastijų ir vietinių valdovų. XIX a. miestą valdė britai, jų valdymo metu Madurajus patyrė sparčią urbanizaciją. Madurajus tapo vienu iš Indijos nepriklausomybės kovos židinių.
