V preteklosti je kraj imel različna imena. Vsa so povezana z zgodovino cerkve.
Večinsko slovensko prebivalstvo je za kraj in cerkev najbolj uporabljalo slovensko poimenovanje: Gora, Marija na Gori, Sv. Marija na Gori. V 18. in 19. stoletju je bilo v rabi tudi poimenovanje Novagora oz. Nova Gora, v času nacistične okupacije pa so kraj poimenovali kot Bergneustift.
Od turških vpadov naprej je bila Ptujska Gora znana tudi kot Črna gora. Ime je povezano z legendo, ki pripoveduje o črnem oblaku s katerim naj bi Marija ogrnila cerkev, da je ne bi našli Turki. Izvor imena Črna gora je povezan tudi z zunanjim izgledom cerkvene zgradbe. Kamen iz katerega je narejena je namreč sčasoma potemnel, zato se je ljudem zdelo, da je cerkev umazana oz. črna. Ime Črna gora se je najbolj udomačilo ob koncu 19. stoletja, za kar je zaslužen Anton Turkuš, ki je leta 1892 po ljudski legendi povzel in objavil pesnitev s tem imenom.
Današnje ime Ptujska Gora se je pojavilo v 19. stoletju. Prvi zapis tega krajevnega imena se je pojavil 15. novembra 1870 v časopisu Slovenski narod (str. 1-2), in sicer v kratkem poročilu neznanega avtorja o študiji Hansa Petschniga (Janka Pečnika), ki jo je ta o cerkvi na »ptujskej Gori« objavil v Izvestjih Centralne komisije za raziskovanje in ohranjevanje stavbnih spomenikov.
