Ustna tradycja mówi, że początkowo figura, zwana wtedy Madonną z Vinski, była czczona w drewnianej kapliczce stojącej na wzgórzu Vinski Vrh, 3 km od miejsca, gdzie dziś znajduje się sanktuarium. Nieustanne zagrożenie ze strony Turków spowodowało, że figura została przeniesiona do Bistricy, gdzie dwukrotnie ją chowano. Po raz pierwszy w 1545 roku proboszcz ukrył ją w chórze parafialnego kościoła. Wkrótce potem proboszcz zmarł, a tajemnicę miejsca przechowywania figury zabrał ze sobą do grobu. Czciciele Maryi długo jej szukali. W 1588 roku została ona odnaleziona dzięki cudownemu światłu wydobywającemu się spod chóru podczas wieczornej modlitwy.

W 1650 roku statua Maryi z Bistricy po raz drugi została ukryta w murach kościoła. Historia się powtórzyła. Znów miejsce jej ukrycia zostało otoczone tajemnicą, a później zapomniane. Ponownie i ostatecznie figurę odnaleziono 15 lipca 1684 roku. W następnych dniach miało miejsce wiele cudownych uzdrowień. Już 16 lipca podczas Mszy św. w kościele sparaliżowana dziewczynka o imieniu Małgorzata odzyskała zdolność chodzenia. Statua została ponownie otoczona czcią i umieszczona na bocznym ołtarzu, gdzie przebywała do czasu, kiedy w 1715 roku, jako dowód wdzięczności od całego narodu chorwackiego za opiekę podczas epidemii dżumy, wybudowano nowy ołtarz główny, na którym umieszczono figurę.

Dzisiejszy wygląd kościoła w Marija Bistrica pochodzi z lat 80. XIX wieku. W tym czasie z woli arcybiskupa Zagrzebia oraz proboszcza parafii Bistrica została podjęta przebudowa sanktuarium. Prace rozpoczęły się 10 maja 1879 roku pod kierunkiem architekta Hermana Bollé, którego projekt został wybrany spośród wielu innych. Stary kościół powiększono i rozbudowano. Podwyższono dzwonnicę, zbudowano też nowe arkady dookoła sanktuarium, a nad nimi pokoje gościnne dla kapłanów. Powstały kaplice św. Józefa i św. Katarzyny. W tym samym czasie powiększono i odnowiono dom parafialny. Kompleks sanktuarium przybrał wygląd fortecy lub zamku na wzgórzu. Jednak podczas prowadzonych prac wydarzyło się nieszczęście. 14 sierpnia 1880 roku, w noc poprzedzającą wielkie święto maryjne, wybuchł pożar, który zniszczył wnętrze kościoła. Uratował się jedynie ołtarz główny z cudowną statuą Madonny. Kościół szybko odbudowano, a papież Leon XIII podarował złocony, bogato zdobiony piedestał dla figury.

Na początku XX wieku sanktuarium zostało obdarzone przywilejami i tytułami. W 1923 roku Ojciec Święty Pius XI nadał kościołowi parafialnemu tytuł bazyliki mniejszej, a 13 lat później (7 lipca 1935 roku) z woli Watykanu arcybiskup Zagrzebia Antun Bauer koronował statuę Czarnej Madonny dwiema koronami: dużą koronowano głowę Matki Bożej, a mniejszą – główkę Dzieciątka Jezus. Korony zostały wykonane na wzór starych koron królów chorwackich i były darem narodu. Z tej okazji do Marija Bistrica przybyło 30 000 pielgrzymów z abp. Alojzym Stepinacem. Podczas tej samej uroczystości Madonna z Marija Bistrica została ogłoszona Królową Chorwatów.

W czasie II wojny światowej wbrew wielorakim trudnościom pielgrzymki do sanktuarium odbywały się nieprzerwanie. W 1942 roku abp Stepinac sprowadził do Bistricy paulinów z Jasnej Góry. Chciał odnowić w Chorwacji działający tu dawniej zakon paulinów i powierzyć im opiekę nad sanktuarium. Niestety z powodu zawirowań wojennych Polacy bardzo szybko opuścili Marija Bistrica.

Po wojnie rząd komunistyczny nękał i prześladował wierzących. Chociaż pielgrzymki zostały zakazane przez władze, pobożny lud je kontynuował. Wielu byłych żołnierzy przybywało do sanktuarium, aby podziękować Maryi za ocalenie życia. Za udział w pielgrzymkach wielu ich uczestników było prześladowanych, bitych i więzionych. Uroczystości w Marija Bistrica aż do końca lat 60. mogły się odbywać tylko wewnątrz sanktuarium.

Sytuacja poprawiła się po 1971 roku, kiedy w Zagrzebiu i Marija Bistrica odbył się Międzynarodowy Kongres Maryjny. Podczas uroczystości do zgromadzonych w sanktuarium pielgrzymów za pomocą przekazu radiofonicznego zwrócił się Ojciec Święty Paweł VI. Kilka miesięcy później biskupi chorwaccy ogłosili Marija Bistrica narodowym sanktuarium Matki Bożej Królowej Chorwacji. Od tamtego czasu liczba pielgrzymów przybywających ciągle wzrasta. Obecnie co roku do sanktuarium przybywa od pięciu do ośmiu tysięcy pielgrzymów. 3 października 1998 roku pielgrzymował tu również Papież Jan Paweł II.