XV amžiuje bažnyčios vidaus sienos buvo tinkuotos ir puoštos bizantinio stiliaus tapyba. Pirmuosius jos fragmentus 2006 metais atidengė polichromijos tyrėjas Vytautas Raila.
Tapybos atodangos rodo, kad bizantinio stiliaus freskomis bažnyčia buvo dekoruota du kartus — vėlesnio laikotarpio tapybos sluoksnis rastas ant užmūrytos pietvakarinio lango nišos, čia išliko trimis ketvirčiais pasisukusio vyro veidas. Buvus du dekoravimo etapus rodo ir tos pačios navos vakarų sienoje skirtingame aukštyje nutapytos draperijos. Apie XV amžiaus bažnyčios interjero dekorą galima spręsti iš rastų freskų fragmentų ir bendrųjų bizantinės sienų tapybos principų. Tapybą sudarė ne mažiau kaip trys horizontalūs registrai. Apatiniame — dekoratyvi kabančią draperiją imituojanti juosta, ėjusi visu bažnyčios interjero perimetru. Virš draperijų vaizduotos visafigūrės patriarchų, Bažnyčios tėvų ir šventųjų figūros, viršutiniame registre — siužetinės kompozicijos. Pavaizduotus asmenis, kaip įprasta bizantinėje dailėje, identifikuodavo įrašai, Trakuose rašyta kirilika. Iš šiuo metu atidengtų tapybos fragmentų geriausiai išlikusi patriarcho Jokūbo figūra vakarinės sienos šiaurinėje navoje. Patriarchas vaizduojamas stovintis po vynmedžiu, virš jo — identifikacinis įrašas kirilika. Įdomi ir neįprasta šio atvaizdo ikonografija: patriarchas vaizduojamas su sūnumis, jų veidai ištapyti ant Jokūbo krūtinės, o sunertos rankos tarsi apglėbia jų menamus kūnus. Vienos figūros per maža, kad būtų galima daryti platesnius apibendrinimus apie ankstyviausią bažnyčios dekoro programą, tačiau itin reta Jokūbo ikonografija bei žinios apie vienalaikę Trakų salos pilies rūmų sienų tapybą leidžia kelti prielaidą, kad Lietuvos Didžiojoje Kunigaikštystėje vėlyvaisiais viduramžiais buvo susiformavusi savita bizantinės sienų tapybos mokykla, gyvavusi iki XV amžiaus vidurio, o galbūt ir ilgiau. Tikėtina, kad kuriame nors kunigaikštystės stačiatikių vienuolyne savo amato išmokę meistrai dirbo valdovui ir galbūt didikams.
Bandant nuspėti, ką vaizdavo viduramžių tapyba, tikslingiausia jos turinį sieti su fundatoriaus Vytauto interesais ir bažnyčios titulu. Viduramžiais bažnyčias puošę paveikslai laikyti beraščių Biblija, į juos žvelgiant tikėjimo tiesos tapdavo akivaizdžios, o vaizdais perteikti pasakojimai — sektinais pavyzdžiais tikintiesiems. Bažnyčios dedikacija Švč. Mergelės Marijos Apsilankymui pas Elzbietą ir to meto dailės praktikos leidžia nuspėti sienų tapybos idėją. Krikščioniškoji tradicija Apsilankymą suvokia kaip senosios ir naujosios sandoros susitikimą ir naujosios sandoros – krikščionybės – viršenybės pripažinimą. Manytina, kad neseniai Krikštą priėmusioje Lietuvoje ši alegorija taip pat buvo nuoroda į pagonybės ir krikščionybės susidūrimą ir pastarosios pergalę. Bažnyčioje šią idėją perteikė būdingas Senojo ir Naujojo Testamentų scenų išdėstymas: vakarinėje pusėje vaizduojama praeitis — Senojo Testamento įvykiai, o rytinėje dalyje — jų išsipildymas — Naujojo Testamento įvykiai ir šventųjų gyvenimo istorijos. Bažnyčios titulą atskleidžianti kompozicija veikiausiai buvo įkomponuota presbiterijoje.
Ankstyviausios žinios apie sienų tapybą yra iš XVII amžiaus pirmosios pusės. 1645 m. kanauninkas Symonas Mankiewiczius paskelbė trumpą Trakų bažnyčios istoriją. Joje rašo, jog kadaise visa bažnyčia buvo senoviškai graikišku būdu ištapyta, tačiau pastačius priebažnytį navose buvusi tapyba uždažyta kalkėmis. Senoji tapyba išlikusi tik presbiterijoje. Po penkerių metų Albertas Vijūkas-Kojelavičius trumpai pakartojo Mankiewicziaus pateiktą informaciją, pabrėždamas, kad graikų papročiu bažnyčios sienos buvo ištisai puoštos tapyba. Nors Kojelavičius apie tapybą rašė būtuoju laiku, nėra jokių žinių apie bažnyčios remontą 1645—1650 m. Todėl manytina, kad presbiterijoje buvusi tapyba užtinkuota bažnyčią atstatant po karo su Maskva, XVII amžiaus septintajame dešimtmetyje. Kadaise bažnyčios sienas puošusi tapyba būdavo prisimenama ir vėliau, dažniausiai ją siejant su stebuklingu, anot legendos, Bizantijos imperatoriaus Emanuelio II Vytautui dovanotu, Trakų Dievo Motinos paveikslu.
