Nors legendos Magadhos istoriją nukelia į II tūkst. pr. m. e., kuomet valdė legendinės Brihadrathų ir Pradjotų dinastijos, pirmoji istorinė dinastija buvo Šišunagų dinastija, valdžiusi nuo VII a. pr. m. e. Ši valstybė buvo gerokai jaunesnė nei senosios indoarijų valstybės, tokios, kaip Kuru ar Pančala. Senoji Magadhos karalystė paminėta Mahabharatoje, Ramajanoe, Puranose.
Šišunagų laikais Magadhoje VI–V a. pr. m. e. gimė dvi įtakingos Indijos religijos: Buda Gautama davė pradžią budizmui, o Mahavira džainizmui. Dėl to ji ypač daug minima budistų ir džainų tekstuose.
Nuo Nandų laikų (IV a. pr. m. e.) Magadha tapo ekspansyvia jėga Pietų Azijoje. Iš pradžių ji užėmė visas šiaurės Indijos valstybėles, sukurdama galingą imperiją. Nandų teritorijos paveldėtoja buvo Maurijų dinastija, kuri sukūrė didžiausią Pietų Azijos istorijoje imperiją, kuri vienintelę trumpam suvienijo visą Indiją iki britų kolonijinio laikotarpio.
Mirus garsiausiam maurijų valdovui Ašokai, III a. pr. m. e. pabaigoje Magadha patyrė krizę. Ji neteko visų pietinių teritorijų (ten įsigalėjo Satavahanos imperija). 185 m. pr. m. e., atėjus į valdžią Šungų dinastijai, neteko ir vakarinių sričių (ten įsigalėjo Graikų-Baktrų karalystė, vėliau – Kušano imperija). Taigi, teritorijos vėl sugrįžo iki istorinės Magadhos sričių.
Po ilgo nuosmukio valdant šungams ir kanvams, Magadha nebeteko valstybingumo 30 m., užkariauta Satavahanų. Tačiau 240 m. prasidėjo antrasis Magadhos atgimimas, sietinas su Guptų dinastija, kuomet valstybė vėl išsiplėtė Pietų Azijoje, o jos mokslas, religija ir filosofija išgyveno savo aukso amžių.
Magadha nustojo egzistuoti 550 m., Guptų imperiją nusiaubus eftalitams.