Hasta nuestros días no han llegado testimonios escritos sobre el origen del kremlin, pero, según la versión oficial, la ciudad de Kazán fue fundada a principios del siglo X. Al principio, el kremlin se llamaba Kerman. No existen fuentes escritas al respecto.

Los hallazgos arqueológicos más antiguos se descubrieron en la parte norte del kremlin, más cerca del Kazanka, donde se ubicaba un antiguo asentamiento fortificado búlgaro, y más tarde, la fortaleza del kanato de Kazán. Los investigadores tienen opiniones divergentes sobre la datación de las estructuras fortificadas de madera: algunos creen que el asentamiento búlgaro fue fortificado ya en el siglo X, otros, solo en el siglo XII. También existen desacuerdos sobre la naturaleza de las fortificaciones: algunos sostienen que las paredes de piedra comenzaron a levantarse en el siglo XII, otros creen que esto ocurrió solo en los siglos XV o XVI tras la reconstrucción del kremlin por orden de Iván el Terrible con arquitectos de Pskov.

Desde mediados del siglo XIII hasta la primera mitad del siglo XV, el kremlin se convirtió en el centro del principado de Kazán dentro de la Horda de Oro. En 1236, las hordas mongolas lideradas por Batu invadieron Bulgaria del Volga y destruyeron su capital. En 1240, Bulgaria, al igual que los principados rusos, quedó bajo el dominio de la Horda de Oro. Parte de los búlgaros se trasladó a la zona de Kazanka y fundó Iske-Kazán, una ciudad a 45 kilómetros de Kazán. En 1370, el príncipe búlgaro Hasan fundó una fortaleza en el lugar del actual kremlin de Kazán, que sirvió como residencia de los príncipes búlgaros hasta 1445.

Tras el asedio de Kazán por Iván el Terrible en 1552, la fortaleza fue destruida. Para la construcción de un nuevo kremlin de piedra blanca, el zar invitó a los arquitectos de Pskov Postnik Yakovlev e Iván Shiryay. La fortaleza se amplió significativamente, se construyeron seis torres de piedra, pero en el siglo XVI solo se logró reemplazar un tercio de las paredes de madera por piedra. El reemplazo completo de las estructuras defensivas de madera por las de piedra se realizó a principios del siglo XVII.

Los maestros de Pskov también levantaron las primeras iglesias ortodoxas del kremlin de Kazán: la catedral de la Anunciación, la iglesia de los santos Cipriano y Justina, la iglesia de Dmitri de Salónica, la iglesia de la Salvación, así como dos monasterios, el de la Trinidad de San Sergio y el de la Transfiguración de Cristo. Después del incendio de 1672, comenzó la construcción de ladrillo, y algunas torres, incluida la de la Salvación, fueron reconstruidas por arquitectos de Moscú.

Después de la revolución de 1917, en las décadas de 1920 y 1930, durante el período de lucha contra la religión, se destruyeron en el kremlin de Kazán el campanario y la iglesia catedral del monasterio de la Salvación, el campanario de la catedral de la Anunciación, la iglesia de los santos Cipriano y Justina, la capilla de la Salvación, se perdieron los iconostasios y reliquias de las iglesias del kremlin. En el período soviético continuó el estudio arqueológico del kremlin, iniciado en el siglo XIX. En la década de 1960 se creó el taller de restauración tártaro. Con la formación de la República de Tatarstán en 1992, el kremlin de Kazán se convirtió en la residencia del Presidente de la República de Tatarstán. En 1993-1994 se desarrollaron las direcciones de reconstrucción y desarrollo del complejo del Kremlin de Kazán. En 1994, por decreto del presidente de Tatarstán, se creó el Museo-Reserva Estatal de Historia, Arquitectura y Arte "Kremlin de Kazán", comenzando un estudio científico sistemático y la restauración del complejo. Se restauraron las murallas defensivas y tres torres, así como la conservación y museificación de los objetos de los siglos XV-XVI. Se inició la construcción de un mausoleo para el reentierro de los restos de los kanes. Durante las excavaciones se descubrió el cementerio del monasterio de la Trinidad y el necrópolis del monasterio de la Transfiguración. Se logró detener la caída de la torre de Syuyumbike. Se restauraron completamente el palacio del gobernador y la iglesia del Palacio, así como cuatro edificios del Patio de los Cañones. En el complejo del Patio Arzobispal se restauró la catedral de la Anunciación. En 1995 comenzaron los trabajos para recrear la mezquita Kul Sharif y la restauración de los interiores de la catedral de la Anunciación.

El 30 de noviembre de 2000, en la sesión del Comité del Patrimonio Mundial de la UNESCO, el kremlin de Kazán fue incluido en la lista del Patrimonio Mundial. Une los logros del arte de la construcción urbana tártara y rusa, en memoria de lo cual se erigió un monumento a los arquitectos en el parque junto a la catedral de la Anunciación. Se instaló una iluminación nocturna para el kremlin, y se abren vistas panorámicas desde las plazas del Milenio y del Palacio, así como desde la presa del Kremlin.