Różanystok pierwotnie nazywał się Tabeńszczyzną albo Krzywymstokiem. Z nadania króla Zygmunta Augusta (przed 1572 r.) i króla Stefana Batorego z 1582 r. majętność ta prawdopodobnie należała do Scypionów del Campo razem z Harasimowiczami, Stockiem (Stocznem) i Grodziszczanami (Grodziskiem). Później właścicielem Krzywego Stoku był Stanisław Tabieński, od którego nabył ją Kazimierz Tyszkiewicz, który testamentem z 24 IX 1652r. przekazał ją swemu bratankowi Szczęsnemu Tyszkiewiczowi.
Szczęsny Tyszkiewicz wraz z żoną Eufrozyną zamówili w 1652 r. u malarza w Grodnie obraz Matki Boskiej i umieścili go w swoim pokoju sypialnym. Gdy w 1658 r. (od 21 XI) zaczęły dziać przy tym obrazie rzeczy, które uznano za cudowne, przeniesiono go do innego pokoju w dworze. Następnie Szczęsny Tyszkiewicz ze swoją małżonką Eufrozyną zbudowali drewniany kościół, do którego przeniesiono słynący łaskami obraz.
W 1661 r. założono tu klasztor dominikanów, którzy odtąd mieli pieczę nad obrazem i coraz liczniej garnącymi się pielgrzymami. Wizerunek Matki Boskiej został poświęcony 21 XI 1662 r. w dniu Ofiarowania NMP przez kanclerza kurii biskupiej ks. Kazimierza Jana Wojsznarowicza. Biskup wileński Aleksander Sapieha w 1668 r. zatwierdził kult obrazu Matki Boskiej Różanostockiej. W latach między 1658 i 1662 nastąpiła zmiana nazwy miejscowości na Różanystok.
W 1759 r. dominikanie rozpoczęli budowę murowanego kościoła na wzór jezuickiej świątyni w Grodnie. W 1785 r. kościół konsekrował sufragan wileński bp Tomasz Ignacy Zienkowicz. Nie był on wykończony. Nie zbudowano jeszcze kopuły oraz dwóch wież. Ukończyli natomiast w 1794 budowę murowanego klasztoru. Po ostatnim rozbiorze Polski Różanystok znalazł się w zaborze pruskim. Prusacy wkrótce zabrali dominikanom wieś Stock, która stanowiła uposażenie klasztoru. Zakonnicy podjęli więc starania o utworzenie w Różanymstoku parafii.
W 1811 r. abp Stanisław Bohusz Siestrzencewicz, metropolita mohylewski erygował w Różanymstoku Parafię pod wezwaniem Ofiarowania NMP i powierzył ją pod opiekę Ojcom Dominikanom.
W 1846 r. władze carskie zamknęły klasztor dominikanów i opiekę nad świątynią i parafią przejęli księża diecezjalni. Dnia 15 IX 1866 r. rząd rosyjski zabrał kościół katolikom i zlikwidował parafię. Kościół razem z cudownym obrazem przekazano prawosławnym, którzy wnętrze świątyni dostosowali do potrzeb kultu w obrządku wschodnim. W 1901 r. Różanystok przekazano mniszkom prawosławnym z Grodna. Za ich czasów najwięcej zrealizowano inwestycji, ale i dokonano największych dewastacji w kościele. Zburzono dwa boczne ołtarze, zniszczono organy i dzwony. W sierpniu 1915 r. mniszki uciekły z Różanegostoku przed nadciągającymi wojskami niemieckimi i zabrały ze sobą słynący łaskami obraz Matki Bożej. W trakcie działań wojennych klasztor zamieniono na koszary, a kościół na magazyn. Katolicy zaraz po wkroczeniu Niemców rozpoczęli starania o odzyskanie kościoła. Oddano im dopiero pod koniec okupacji.
W listopadzie 1918 r. kościół został przekazany duchowieństwu katolickiemu. Na proboszcza odrodzonej parafii, biskup wileński Jerzy Matulewicz powołał ks. Witolda Sarosieka. W wyniku starań biskupa i proboszcza do Różanegostoku przybyli w listopadzie 1919 r. Salezjanie. Odtąd opiekowali się oni parafią i rozwinęli szeroką działalność oświatową i wychowawczą.
Salezjanie starali się o odzyskanie wywiezionego obrazu Matki Boskiej. Gdy się to nie udało zamówili nowy obraz na wzór poprzedniego. W dniu 8 IX 1929 r. odbyło się uroczyste wprowadzenie do świątyni nowego obrazu Matki Bożej, namalowanego w 1928 roku przez Jana Sawczyka w warszawskim zakładzie Włodzimierza Tura. Dnia 28 VI 1981 r. odbyła się koronacja słynącego łaskami obrazu Matki Boskiej Różanostockiej. Uroczystościom przewodniczyli: ks. kard. Franciszek Macharski, abp Henryk Gulbinowicz i bp Edward Kisiel. W 1987 r. Ojciec św. Jan Paweł II nadał kościołowi w Różanymstoku tytuł Bazyliki Mniejszej.
Mimo iż w 1954 r. władze państwowe zlikwidowały gimnazjum salezjańskie oraz cały ich zakład, to jednak obecnie, w nowych warunkach, Salezjanie nadal prowadzą nie tylko parafię, ale i szeroką działalność wychowawczą i oświatową.