Velehradská bazilika byla postavena na "zelené louce". S původním velkomoravským Veligradem nemá mnoho společného. Novým Velehradem bylo nazváno město Uherské Hradiště. Jádro Veligradu bylo zase ve Starém Městě. Nicméně v době velkomoravské zde existovalo osídlení a navazovalo na aglomeraci opevněných dvorců veligradských.
Velehrad je jedním z nejvýznamnějších poutních míst Moravy. Historie tohoto místa se začala psát před více než 800 lety, kdy do údolí říčky Salašky přišlo prvních 12 cisterciáckých mnichů, aby nedaleko obce Veligrad (dnešní Staré Město) vybudovali svůj klášter. Právě na základě své polohy dostal klášter své jméno a stal se záhy nositelem mnohem starší duchovní tradice, která sahá až do 9. století, kdy na Moravu přišli slovanští věrozvěstové Konstantin a Metoděj, díky čemuž již po staletí na Velehrad proudí tisíce poutníků.
Zakladateli kláštera byli moravský markrabě Vladislav Jindřich se svým bratrem Přemyslem Otakarem I. a olomoucký biskup Robert. Výstavba kostela byla zahájena patrně v letech 1210 – 1215. Jako většina cisterciáckých kostelů přijal patrocinium Nanebevzetí Panny Marie. (Spolupatronát Cyrila a Metoděje byl připojen až v roce 1932 dekretem papeže Pia XI. Titulem bazilika byl chrám vyznamenán v roce 1928 z rozhodnutí papeže Pia XI.).
Původní románsko-gotická bazilikální stavba byla budována podle stavebních tradic cisterciáků, které charakterizovala krása prostých linií a střídmá výzdoba. Devadesát devět metrů dlouhá stavba byla rozvržena na půdorysu latinského kříže. Východní stranu uzavírala pětice apsid. V této podobě se kostel do dnešních časů nedochoval v důsledku tragických událostí, jež v průběhu dějin cisterciácký klášter postihly. V roce 1421 vypálili velehradské opatství moravští husité z Nedakonic. Klášter 150 let chátral. Nesnadného úkolu obnovy se ujal až opat Ekard ze Schwöben ve druhé polovině 16. století. Středověkou podobu však kostel ztratil až v důsledku obrovského požáru, který v klášteře vypukl v roce 1681. V důsledku této pohromy byl kostel radikálně přestavěn. Stavba byla zkrácena o chrámové průčelí s románským ústupkovitým portálem a nahrazena novým, jemuž dominují dvě věže. Boční lodě baziliky byly přezděny příčkami s pilastry, a tak vzniklo 14 samostatných postranních kaplí, z nichž 10 má oltáře a pod podlahou krypty. Z křížení lodí byla snesena 100 metrů vysoká renesanční věž a byla nahrazena kupolí s nízkou věží zvanou lucerna. Nyní je tedy bazilika dlouhá 86 m. Přes radikální zásahy si kostel uchoval ve svých proporcích a půdorysném schématu charakter románsko-gotické stavby.
Významnou novodobou událostí pro velehradskou baziliku byla návštěva papeže Jana Pavla II., jehož výslovným přáním pro krátkou, zcela mimořádnou, návštěvu Československa bylo připutovat právě na Velehrad.
Mons. Jan Graubner, arcibiskup olomoucký: "Z odvážného díla soluňských bratří Cyrila a Metoděje vyrostla kultura našeho národa. Evangelium, které hlásali našim předkům, ovlivnilo naši kulturu mnohem více, než si někdy připouštíme. Radost a naděje, svoboda i jasný směr k vysokému ideálu, rozvinuté bohatství ducha i společenství, které dovede slavit... to všechno patří k dědictví otců vyrostlém z darů Ducha zprostředkovaným křesťanskou vírou."
