I fondatori del monastero furono il margravio moravo Vladislav Jindřich con suo fratello Přemysl Otakar I e il vescovo di Olomouc Robert. La costruzione della chiesa fu iniziata probabilmente tra il 1210 e il 1215. Come la maggior parte delle chiese cistercensi, adottò il patrocino dell'Assunzione della Vergine Maria (il compatrono di Cirillo e Metodio fu aggiunto nel 1932 con un decreto di Papa Pio XI). Il titolo di basilica è stato conferito alla chiesa nel 1928 con decreto di Papa Pio XI).

L'originale edificio basilicale romanico-gotico fu costruito secondo le tradizioni costruttive dei cistercensi, caratterizzate dalla bellezza delle linee semplici e dalla modestia delle decorazioni. L'edificio, lungo novantanove metri, era disposto a croce latina. Il lato orientale era chiuso da cinque absidi. La chiesa non è sopravvissuta in questa forma a causa dei tragici eventi che hanno colpito il monastero cistercense nel corso della storia. Nel 1421, gli ussiti moravi incendiarono l'abbazia di Velehrad. Il monastero decadde per 150 anni. Solo nella seconda metà del XVI secolo l'abate Ekard di Schwoben intraprese il difficile compito di restaurarlo. Tuttavia, la chiesa perse il suo aspetto medievale solo a causa di un enorme incendio scoppiato nel monastero nel 1681. A seguito di questo disastro, la chiesa fu radicalmente ricostruita. L'edificio fu accorciato dalla facciata della chiesa con un portale romanico di concessione e sostituito da uno nuovo dominato da due torri. Le navate laterali della basilica furono ricostruite con transetti a pilastri, creando 14 cappelle laterali separate, 10 delle quali con altari e cripte sotto il pavimento. La torre rinascimentale, alta 100 metri, fu abbattuta dall'incrocio delle navate laterali e sostituita da una cupola con una torre bassa chiamata lanterna. La basilica è ora lunga 86 metri. Nonostante i cambiamenti radicali, la chiesa ha mantenuto il carattere di edificio romanico-gotico nelle proporzioni e nella pianta.

Nel 1784 il monastero di Velehrad fu sciolto da Giuseppe II. La proprietà del monastero fu smantellata, i terreni del monastero cambiarono proprietario e la chiesa del monastero divenne una chiesa parrocchiale. L'edificio era molto fatiscente e non c'erano fondi per la sua manutenzione. La chiesa fu ricostruita nel contesto del crescente culto di Cirillo e Metodio e fu restaurata durante i millenni di Cirillo e Metodio nel 1863 e nel 1885. Un ulteriore sviluppo fu garantito dall'arrivo dei gesuiti a Velehrad nel 1890. Durante la loro amministrazione, l'edificio fu messo in sicurezza contro l'ingresso dell'umidità negli anni Venti e Trenta. A ciò è legata la scoperta dei sotterranei di Velehrad, aperti al pubblico prima dello scoppio della Seconda Guerra Mondiale. Tra il 1935 e il 1938 l'interno della chiesa fu restaurato. L'avvento al potere dei regimi totalitari ha impedito lo sviluppo del luogo di pellegrinaggio per decenni, anche se sono state effettuate le riparazioni più necessarie (ad esempio la messa in sicurezza statica della volta e la sostituzione del tetto e della copertura).

I gesuiti tornarono a Velehrad nel 1990 e Papa Giovanni Paolo II venne a Velehrad. Da allora si è assistito a un graduale rinnovamento materiale e spirituale di Velehrad, il cui culmine è rappresentato dal progetto Velehrad - centro di dialogo culturale tra Europa occidentale e orientale.