Świątynia ufundowana została przez Jana Klemensa Branickiego w 1758 jako katolicka kaplica przydrożna pod wezwaniem św. Marii MagdalenyP. Chomik, Kaplica pw. św. Marii Magdaleny w Białymstoku w: M. Karczewska, M. Karczewski, Cmentarz wielowyznaniowy na wzgórzu Św. Marii Magdaleny w Białymstoku. Historia miejsca, Białystok–Poznań 2012, s. 27–31.. Wyświęcona została przez księdza Ignacego Massalskiego, późniejszego biskupa wileńskiegoJ. Tołłoczko, Ł. Włoch, Charakterystyka architektoniczna kaplicy pw. św. Marii Magdaleny w: M. Karczewska, M. Karczewski, Cmentarz wielowyznaniowy na wzgórzu Św. Marii Magdaleny w Białymstoku. Historia miejsca, Białystok–Poznań 2012, s. 33.. Kaplica należała do altarii św. Rocha, którą hetman Branicki ufundował w 1750. Świątynia została wzniesiona w stylu barokowym w formie rotundy na wysokim wzgórzu, które w XVIII w. położone było poza obrębem miasta.
W związku z przepełnieniem istniejących cmentarzy, prawdopodobnie w 1807 przy kaplicy powstał nowy cmentarz katolicki, wówczas nazywany parafialnym. Według przypuszczeń księdza Tadeusza Krahela w 1814 wydzielono na cmentarzu część unicką i prawosławną.