Kazanj su osnovali Volški Bugari negdje u periodu od 11. do 13. vijeka. Zvanično se za godinu osnivanja uzima 1005. 

Gradska tvrđava (kremlj) potiče iz 11. vijeka. Grad je bio osnovan kao granična tvrđava Volške Bugarije a kasnije je postao glavni grad i trgovinski centar moćnog tatarskog Kazanjskog kanata od 1438, i prvi neruski grad koji je car Ivan Grozni 1552. pripojio ruskom carstvu. Ivan Grozni je uništio grad i masakrirao dobar dio stanovništva, a kazanjskog kana nasilno sproveo u hrišćanstvo.

Poslije požara 1579. ispod grada je po legendi otkrivena čudotvorna ikona Bogorodica Kazanjska. Petar Veliki je ovde osnovao brodogradilište Kaspijske flote u ranom 18. veijku.

Grad je uništen 1774. tokom pobune kozačkog atamana Jemeljana Pugačova. Carica Katarina Velika je naredila ponovnu izgradnju grada i dozvolila izgradnju džamija. U 19. vijeku grad je postao industrijski centar srednjeg toka Volge.

U Kazanju je 1870. odštampana prva verzija knjige nepoznatog autora „Ispovesti ruskog hodočasnika svome duhovnom ocu“, koja je kao klasik istočnohrišćanske duhovnosti prevedena na mnoge jezike.

Poslije Revolucije 1905, Kazanj se razvio u centar tatarske kulture. Godine 1920. Kazanj je proglašen za glavni grad Autonomne tatarske sovjetske socijalističke republike. Za vrijeme Drugog svetskog rata neke fabrike vojne industrije su premještene u Kazanj. U gradu su se od tada proizvodili tenkovi i avioni.

Univerzitet u Kazanju je jedan od najstarijih i najznačajnijih ruskih univerziteta na kome su svojevremeno studirali Lenjin i Tolstoj.

Istorijska gradska tvrđava (kremlj) je 2000. godine ušla na listu Svjetske baštine UNESKO-a. Tokom iskopavanja kremlja pronađen je češki novćić koji datira u 10. vijek (kovan između 920.-930.) sa likom sv. Vaclava, što govori u prilog da je bio Kazanj duže vreme jak trgovski centar.