Po powstaniu w 1831 roku w Trokach zaczęło przybywać mieszkańców wyznania prawosławnego, a wspólnota potrzebowała cerkwi. Decyzję o jej budowie za datki parafian oraz przy wsparciu Marii Aleksandrownej, żony cesarza Rosji, która przekazała w darowiźnie 6000 carskich rubli, podjęto w 1861 roku. Za zakończenie prac budowlanych inżynier Polozovas otrzymał od cesarzowej złoty pierścień z kamieniami szlachetnymi. Cerkiew, o tradycyjnej formie i strukturze, została poświęcona w 1863 roku. Nadano jej tytuł Narodzenia Przenajświętszej Bogurodzicy.
Obecnie ta świątynia prawosławna harmonijnie wtapia się w architektoniczną mozaikę Trok. Cerkiew wznosi się na jednym ze wzgórz na półwyspie, na przecięciu ulic Witolda i Maironio. Każdy zainteresowany może obejrzeć zewnętrzną architekturę budynku oraz jego drobiazgowo dekorowane wnętrza.
