De kathedraal werd tussen 1555 en 1560 gebouwd. De volledige naam van het kerkgebouw luidt Sobor Pokrova, tsjto na rvoe (Собор Покрова, что на рву), hetgeen "Kathedraal van de voorbede van de Moeder Gods op de greppel" betekent. De Pokrovkathedraal verving een oudere verlaten kerk op dezelfde plaats. De kerkwijding vond plaats op 12 juli 1561.

Er wordt verteld dat Ivan de architect, Postnik Jakolev, bijgenaamd Barma de mompelaar, na voltooiing van zijn werk vroeg of hij een nog mooier gebouw kon maken. Toen de architect bevestigend antwoordde, liet de tsaar hem de ogen uitsteken, om er zeker van te zijn dat de Pokrovkathedraal het mooiste gebouw zou blijven. Dit verhaal is echter zeer twijfelachtig want de architect heeft daarna nog andere gebouwen ontworpen. Hetzelfde verhaal wordt verteld over de maker van het astronomisch uurwerk van Praag.

Vier jaar na de dood van Ivan IV werd aan de noordoosthoek van de kathedraal een kerk gebouwd, vermoedelijk door dezelfde architect. In opdracht van Tsaar Fjodor werden de relikwieën van de heilige dwaas Vasili (ofwel Basilius) 1588 in eerdergenoemde kerk geplaatst, die naar deze heilige genoemd werd. Vasili, dwaas in Christus, genoot grote verering en omdat in deze kerk dagelijks diensten gehouden werden, in tegenstelling tot de andere kerken die deel uitmaken van de kathedraal, ging men deze kathedraal steeds vaker "de kerk van Vasili de dwaas", in het Nederlands Basilius de Zalige, noemen. Onder deze naam heeft dit bouwwerk meer internationale bekendheid.

In 1919 werd de kerk geconfisqueerd door de bolsjewieken en gesloten voor herstelwerkzaamheden. Pjotr Baranovski leidde de werkzaamheden die tot 1929 duurden. De enige manier om de kerk aan de sloopwoede van de bolsjewieken te doen ontsnappen was haar om te vormen naar een museum; een museum ter gedachtenis aan de Russische verovering van Kazan in dit geval. In 1929 werden de klokken van de kerk weggehaald en gaf Jozef Stalin opdracht om het Rode Plein schoon te vegen van kerken voor een geplande parade. Hierdoor sneuvelde de Kazankathedraal en ook de Pokrovkathedraal stond op de nominatie te worden gesloopt, daar Stalin (mogelijk op suggestie van de directeur van het herconstructieplan van het Rode Plein; Lazar Kaganovitsj) het jammer vond dat deze verhinderde dat zijn soldaten en tanks het plein op massale wijze konden verlaten tijdens parades. Er kwam een groot protest op gang en Eleanor Roosevelt bood zelfs aan om het hele gebouw af te breken en over te brengen naar de Verenigde Staten, hetgeen werd afgewezen. Architect Baranovski was echter instrumenteel in het protest tegen het besluit. Volgens sommige verhalen ging hij op de treden van het gebouw staan en dreigde hij zijn keel door te snijden en liet hij een scherpgesteld telegram naar de Sovjetregering sturen, volgens andere verhalen viel hij op zijn knieën voor het centrale comité van de CPSU om er maar voor te zorgen dat het gebouw bleef staan. Hoe het ook zij, Stalin hief het besluit op, maar Baranovski kreeg in 1933 wel een veroordeling voor "anti-sovjetpropaganda" aan zijn broek en werd voor 3 jaar naar de West-Siberische stad Mariinsk gestuurd om er dwangarbeid te verrichten (met bijbehorende status van oedarnik en een daaropvolgende 101ste kilometerbeperking). In 1936 werd het standbeeld voor Dmitri Pozjarski en Koezma Minin, die het Russische vrijwilligersleger leidden tegen de Poolse invasietroepen tijdens de Tijd der Troebelen, verplaatst van het midden van het Rode Plein naar een plek vlak voor de kathedraal, zodat de troepen er makkelijker langs konden paraderen.

Aan het onderhoud van de kathedraal werd net als bij de meeste kerken in de Sovjet-Unie nauwelijks wat gedaan, zodat het gebouw over de loop van de tijd sterk verviel. In 1990 werden de klokken weer teruggehangen. De huidige klokken dateren van 1547 tot 1996 en komen uit de Oeral, Jaroslavl, Moskou, Frankrijk, Nederland, Duitsland en West-Wit-Rusland. Op 14 oktober 1991 werd de eerste dienst weer gehouden in de kerk. Er kwam echter geen regelmatige dienst en de kathedraal vormt tot op heden onderdeel van het Nationaal Historisch Museum. De kathedraal werd rond de eeuwwisseling gerestaureerd en is opgenomen op de Werelderfgoedlijst van UNESCO.