Nowe Kawkowo jest wsią położoną na północny zachód od Olsztyna, lokowana została w drugiej połowie XIV wieku przez kapitułę warmińską jako wieś kościelna a jej dawna nazwa to Neu-Kockendorf. Pierwsza świątynia uposażona już była w akcie lokacyjnym tej wsi który pochodzi z 21 stycznia 1380, w tym także roku konsekrował ją biskup Jan III Sorbon a poświęcono ją ku czci św. Janowi w Oleju.
Budowla był często modernizowana i odnawiana, w roku 1664 dobudowano drewnianą wieżę dzwonniczą. Inne remonty miały miejsce w XVIII i XIX w. oraz w 1925 r., kruchta i zakrystia zostały dobudowane wałśnie na początku XX w. Wszystkie te prace spowodowały, że z pierwotnego wyglądu tego obiektu zachowały się tylko fragmenty korpusu wykonanego z kamieni polnych łączonych z cegłą.
Kościół wybudowano w stylu późnogotyckim, salowy, murowany do połowy wysokości z kamienia polnego a powyżej ław okiennych i w narożach z cegły. Świątynia jest orientowana wzniesiono ją na rzucie prostokąta z zakrystią od północy i kruchtą od południa. Wspomnianą wieżę natomiast wybudowano po stronie zachodniej, jest ona dwukondygnacyjna drewniana o konstrukcji słupowej i oszalowana deskami, wzniesiono ją na rzucie kwadratu ze ścianami nachylonymi ku górze. Na szczyt wieży umieszczono chorągiewkę z datą 1870 a na sygnaturce wieńczącej szczyt wschodni znajduje się chorągiewka z rokiem 1857, są to lata kolejny prac restauracyjnych.
Wewnątrz kościoła godny uwagi jest przede wszystkim barokowy ołtarz główny wykonany w 1866 r., umieszczono w nim obraz Nawiedzenia Najświętszej Maryi Panny i św. Jana w Oleju oraz figury świętych Piotra i Pawła. Warto również zobaczyć dwa ołtarze boczne z końca XVIII w., barokową ambonę z przedstawieniami Chrystusa i czterech Ewangelistów wykonaną około 1700 r. czy chrzcielnicę z XVII w. W kościele znajdują się także cenne zabytki sztuki złotniczej.
Pewną ciekawostką jest teren przykościelny gdyż możemy tam odnaleźć resztki starego cmentarza i aż trzy krzyże misyjne; pierwszy pochodzi z 1936 r. natomiast dwa pozostałe odnoszą się do czasów współczesnych.