Velehrad az egyik legismertebb zarándokhely Morvaországban. Feltehetően azonos a morva uralkodók egykori székhelyével és azzal a hellyel, ahonnan Cirill és Metód a kereszténységet kezdték el terjeszteni. Velehradon állt Metód pompás székesegyháza, ahová azután eltemették.
A magyarok rajtaütései következtében az egykori nagymorva település elpusztult, ezért ma már nem lehet biztosan megállapítani, hol lehetett a székesegyház, illetve a sír. A két szláv apostol Szent Benedekkel együtt Európa védőszentjei, így Velehrad jelentősége túlnyúlik Csehország határain.
A jelenlegi Velehrad történetének kezdetei a 13. század elejére esnek, amikor Vladislav Jindřich morva őrgróf és bátyja, I. Přemysl Ottokár cseh király megalapították az első cisztercita kolostort Morvaországban. Az első tizenkét cisztercita szerzetes 1205-ben érkezett a cseh Plasy településről Velehradra.
A 13. század közepére készült el kora román – gótikus stílusban a Szűz Mária Mennybemenetele-templom és a kolostor. A templom egy öthajós, pompás bazilika volt, száz méteres hosszúságával kora legnagyobb templomának számított. A bazilika egyes részei máig fennmaradtak – a templom keleti oldalán lévő öt apszisból megmaradt három (a középső a legjelentősebb, melyet szép román díszítőszegély ékesít), és az épület mai szintje alatti kőtárban láthatók a templom román kori alapjai.
A 15. században a kolostort a husziták felégették, az ezt követő évszázadokban néhányszor átépítették. Mai külsejét a 17. és 18. század fordulóján nyerte el. A barokk átalakítás építésze ismeretlen, a stílus alapján Giovanni Pietro Tencallónak tulajdonítják. Nem ismerjük azokat a művészeket sem, akik az épület belső díszítését végezték. A monumentális barokk homlokzatot két torony egészíti ki, a templom padlózatát feltöltötték, két méterrel megemelték.
II. József császár egyházi reformja idején a cisztercita kolostort felszámolták. A híres bazilika jelentéktelen vidéki templommá vált. Állapota egyre romlott, a márványoszlopokkal díszített káptalani teremben lóistálló volt. Velehrad felújítására a 19. század második felében, Cirill és Metód morvaországi missziójának millenniumi évfordulóján rendezett ünnepségek kapcsán került sor.
1890-ben jezsuiták érkeztek Velehradra, akik leszámítva a kommunizmus negyvenéves időszakát, amikor is a kolostort bezárták, máig itt maradtak. 1927-ben XI. Pius pápa értékelte Velehrad jelentőségét a Cirill és Metód-hagyomány, illetve az unionizmus szempontjából, amikor a templomot kis bazilika rangra emelte. 1985-ben, Szent Metód halálának ezeregyszázadik évfordulóján II. János Pál pápa Arany rózsát adományozott a bazilikának (ilyen megtiszteltetésben csak néhány templom részesült a világon). II. János Pál pápa itt kezdte meg 1990. évi első csehországi látogatását.