Gali būti, kad dar kunigaikščio Kęstučio, kuris buvo tolerantiškas kitoms religijoms, laikais Naujuosiuose Trakuose stačiatikiai pasistatė Skaisčiausios Dievo Motinos gimimo cerkvę ir vienuolyną. 1981 m. tyrinėtos cerkvės liekanos, bet liko neaišku ar ji statyta iki XIV a. pb. ar vėliau. Apie statybą nieko nežinoma, tik tai, kad prie cerkvės 1612 m. buvo varpinė ir koplyčia, kuri minima ir 1619 m. Greičiausiai cerkvė sudegė 1655 m. per karą su Rusija ir Švedija. 

Stačiatikių vienuolyno su cerkve buvimas pietinėje dabartinio Trakų pusiasalio dalyje, leidžia daryti prielaidą, kad XIV a. pabaigoje šalia galėjo būti tuometinio Naujųjų Trakų miesto dalis prie medinės pilies. Tuo tarpu pastatytoji cerkvė, nors ir nebuvo vadinama „piatnicka", kaip kituose miestuose, ir nestovėjo prie turgaus aikštės, bet buvo reikalinga tiek čia pat įsikūrusiems, tiek ir atvykstantiems į Trakus rusų pirkliams, kurių tuo metu, LDK esant dideliems rusų žemių plotams, galėjo būti ne taip jau mažai. Ši cerkvė su vienuolynu buvo pastatyta už istoriniuose šaltiniuose minimo pietinio miesto pylimo, tad ji, kaip ir katalikiškoji Trakų parapijos bažnyčia, pastatyta strategiškai svarbioje vietoje, buvo viena Naujųjų Trakų gynybos komplekso grandžių, sauganti įvažiavimą į miestą, išlaikydama tradicinę stačiatikių cerkvių su vienuolynais Rusijos miestuose gynybinę funkciją.

Skaisčiausios Dievo Motinos gimimo cerkvės ir vienuolyno teritorijoje besikuriantys atvykę pirkliai ir amatininkai suformavo pirmąją Trakuose stačiatikiškąją jurisdiką. Jiems kurtis rimta paskata ir garantas buvo artimi Lietuvos santykiai su Rusia ir didžiųjų kunigaikščių stačiatikės žmonos. Cerkvė ir vienuolynas visada priklausė Lietuvos didiesiems kunigaikščiams, kurie vis kartodavo ankstesnes privilegijas išskirdami ją iš metropolito pavaldumo.

1384 m. rugpjūčio 23 d. kunigaikštis Vytautas, stačiatikės Jogailos motinos Julijonos prašomas, savo krikšto proga suteikė cerkvei ir vienuolynui Trakų (dabar Bernardinų) ežero lanką iki Didžiojo kelio, kur, pažymint ribas, ant kalvos buvo padėtas akmuo. Kitas akmuo padėtas už ežero, priešais pirmąjį akmenį. Riba ėjo iki vieškelio ir vieškeliu iki miesto. Čia Vytauto privilegija buvo suteikta ir žemė už žvėryno, vadinama Melovščizna, prie Galvės ir Galvelio ežerų. Dokumento tekstas buvo įrašytas į vienuolyno „Evangelijos" foliantą. Žygimantas Kęstutaitis 1435 m. pakartojo privilegiją vienuolynui, kuria, kaip ir anksčiau, vienuolynas buvo atleistas nuo pavaldumo metropolitui. 
1526 m. Žygimantas Senasis vienuolyną atidavė globoti savo rūmų iždininkui Ivanui Andriejavičiui (Soltanui). 1530 m. šio vienuolyno cerkvė buvo jau be šventiko. Iš to galima spręsti, kad vienuolynas tuo laiku buvo jau menkas, o gal ir stačiatikių Trakuose buvo sumažėję. Iš 1604, 1619, 1653 m. dokumentų matyti, kad tada, kaip ir XVI a. vienuolynas su cerkve jau buvo praradęs dalį fundacinių žemių, vienuoliai nebetekę pajamų, o naujai paskirtam archimandritui leista per teismą ieškoti buvusių cerkvės sklypų. 1683 m. Vladislovas Vaza, Kijevo metropolito prašomas, prijungė šią ir Prisikėlimo cerkves su jų žemėmis prie bazilijonų šv. Trejybės vienuolyno Vilniuje.

Trakų Skaisčiausios Dievo Motinos cerkvės kapinės yra XVI a. Tokių griautinių kapinynų atsiradimas yra būdingas reiškinys didžiausiuose to laikotarpio besikuriančios valstybės centruose, kur buvo įsikūrusios slavų kolonijos.