O nastanku romarske cerkve na Ptujski Gori pripoveduje zgodba o slepi hčeri bogatega vurberškega grofa za katero ozdravljenje sta starša vsak dan prosila Marijo.
Zgodovinski viri pričajo, da je bila cerkev kolektivna ustanova pomembnih predstavnikov štajerskega plemstva na čelu s Hermanom II. Celjskim. Nastala je po porazu krščanske vojske v bitki proti Turkom leta 1396 pri Nikopolju. Štajerski plemiči so jo zgradili v zahvalo, ker so se iz bitke domov vrnili živi. Cerkev naj bi med leti 1396-1400, najverjetneje pa leta 1398, začela zidati Bernard III. Ptujski in njegov bratranec in skrbnik grof Ulrik IV. Walsee, kot donatorji so se pridružili grofje Celjski, nato pa tudi grofje Stubenberški, dediči Ptujskih. Cerkev je bila do leta 1410 v veliki meri zgrajena, do ok. 1420 pa je bila popolnoma opremljena.
Za prvo pisno pričevanje o cerkvi in njeni podobi je poskrbel potopisec Paolo Santonino. V svojem popotnem dnevniku iz leta 1487 je takole opisal ptujskogorsko cerkev: „Cerkev blažene Marije so ustanovili ptujski gospodje, in sicer z velikimi stroški, saj je zunaj in znotraj pozidana s kvadri, nalomljenimi iz žive skale in obdelanimi s čudovito in prelepo kamnoseško veščino, njeni trdni oboki pa se dvigajo zelo visoko na več kamnitih stebrih (slopih). V njej je deset oltarjev in vsak med njimi ima kamnit kip tistega svetnika, v čigar ime je postavljen. Svetoskrunske turške roke so jih vse podrle z njihovega prostora na tla in jim brezbožno odbile ude.”
Cerkvena stavba, zgrajena iz treh vrst peščenjaka (iz sivega ptujskogorskega, viniškega ter peščenjaka iz bližine sv. Barbare pri Borlu), do leta 1487, ko je Ptujsko Goro obiskal Paolo Santonino, ni doživela večjih sprememb, z izjemo oltarne opreme, ki je bila močno poškodovana zaradi turškega napada leta 1475. Po letu 1487 je zahodni del cerkve močno prizadel požar. Z obnovitvenimi deli leta 1491, ki jih je vodil tedanji kaplan Ulrik Mettlinger, je na Ptujski Gori nastala tudi slikarska dekoracija. Najobsežnejša je bila v Križevi kapeli na južnem delu stavbe. Freske v Križevi kapeli pod korom so sicer začele nastajati še pred smrtjo prvega kaplana Nikolaja leta 1424, cerkev pa so slikami ponovno okrasili ok. leta 1491.
Cerkev, ki je že od vsega začetka bila mišljena kot romarska, v kateri se bodo lahko verniki obračali h glavni tolažnici in priprošnjici pred Bogom, je cerkvenopravno pripadala župniji v Lovrencu na Dravskem polju. Po smrti Friderika IX. Ptujskega (1438), zadnjega iz rodbine Ptujskih, je ptujskogorsko cerkev podedovala družina Stubenberg. Ti so se kasneje pridružili reformaciji in na Ptujski Gori postavili protestantskega duhovnika, ki je tu bival do leta 1574. V času protireformacije so patronat nad cerkvijo prevzeli deželni knezi Habsburžani. Nadvojvoda Ferdinand je leta 1615 lovrenško župnijo podelil jezuitom iz Leobna na Gornjem Štajerskem. Ti so posedovali župnijo in cerkev do razpustitve jezuitskega reda leta 1773. Z reformami Jožefa II. je ptujskogorska cerkev leta 1786 postala sedež nove župnije. Škofijski duhovniki so jo upravljali do leta 1937, ko so jo prevzeli ptujski minoriti.
Po drugi svetovni vojni, leta 1951, je komunistična oblast cerkev zapečatila in v njej prepovedala opravljanje bogoslužja. Leta 1952 je bila cerkev razglašena za kulturnozgodovinski spomenik, funkcija cerkve pa je bila spremenjena v muzej. Leta 1957 so upravljanje cerkve spet prevzeli ptujski minoriti in v cerkvi je spet oživelo bogoslužje.
8. decembra 2009, na praznik Brezmadežne, je papež Benedikt XVI. podpisal listino, s katero je cerkev Marije Zavetnice na Ptujski Gori povzdignil v baziliko („basilica minor”). S tem so se uresničila večletna prizadevanja bratov minoritov, da bi se ptujskogorska cerkev uvrstila „med izbrane”.
