W ciągu wieków wieś ta miała wiele nazw: Vogstdorf, Voythsdorff, Voytsdorff, Voygtsdorf, Voytsdorf, Woitoua, Woigtsdorf, Fitogsdorff, Wytowo, Wotowno, Voigsdorff, Woigtsdorf i Fittigsdorf.
Wieś założyła Kapituła Warmińska następującym dekretem w dniu 18.08.1359 (V nr 2):

1359, 18 sierpnia Frauenburg (Frombork). (Zapis dla Henryka, syna wójta Kapituły Ernsta, 45 łanów k. Klebarka).
W imieniu Pana. Amen. Kościół jest zobowiązany służby swoich wiernych wynagradzać. Jesteśmy zdania, że każdy, kto dla Kościoła dużo i wiernie wykonywał swoje obowiązki, tym bardziej winien być wynagradzany.
Dlatego chcemy my, Hartmodus proboszcz, Hermann dziekan, Jan kustosz i Tyło kantor i cała kapituła katedralna kościoła warmińskiego, zapoznać wszystkich, którzy potrafią czytać, ażeby dojrzale na to zwrócili uwagę. Temu okazałemu rycerzowi, Panu Heinrich (Henrykowi), synowi zmarłego żołnierza Ernesti, który był wójtem kapituły, za pomocą Boga nabył właściwości i stał się zasłużonym dla wiernych i kapituły, i chcemy pana Heinricha obficie wynagrodzić i przyznać jemu i prawnym spadkobiercom 40 łanów lasu i 5 łanów puszczy wraz z małymi i wielkimi sądami nad szyją i ręką na prawie chełmińskim do dobrego użytku w ramach tu poniżej opisanej granicy. Ponieważ wolnizna za tamtych chłopów się skończyła, płaci na święto Bożego Narodzenia czynsz w postaci 2 kamieni wosku na świece do katedry. On jednak będzie dożywotnio zwolniony z jednego kamienia. Ma dożywotnie prawo rybitwy z małymi narzędziami na własną potrzebę w jez. Ammelink (Klebarskie), a jego spadkobiercy w jez. Kukelinge (Linowskie). Granicami są: począwszy od Trauziken (Track) w prostej do granicy terenu biskupiego, w górę aż do rzeki Zurtheke, wzdłuż rzeki w dół, aż do palika granicznego, stamtąd prosto aż do wsi Cleberg, i po prostej do początku. W obrębie granicy jest 40 łanów, a nie więcej.
Potwierdza się i zaopatrzą się w pieczęć naszej kapituły.
Data Vrowenburg (Frombork) 18 sierpnia 1359. Dzień męczennika Agapiti.

Początkowo nie była to wieś, tylko majątek szlachecko-chełmiński. Do 1.02.1478 r. właścicielem majątku był Albrecht von Wittchenwalde, od którego Kapituła odkupiła cały majątek i przekształciła go w wieś czynszową. Te zakupione łany zostały tak obsadzone: Grofikop posiadał 3,5, Peter i Caspar po 3, Urban, Matzke, Cleyne, Hanke, Steynberg, Symon, Merten, Bartolmewis, Nickel i Jorge po 2 łany, Austen 1,5 łana, Kreczmer 1 łan i sołtys 0,5 łana. Odłogiem leżały 2 łany. Kwota za sprzedane łany będzie płacona dopiero, gdy Carlo, syn Niklisa Wittchenwalde, przedłoży decyzję sądu w Gilgenburg (Dąbrówka) o zamiarze sprzedaży tych łanów. W dniu 13.02.1478 r. przedkłada on taką decyzję sądową. Pozostała kwota ma być zapłacona 7.02.1479 r. Przywilej lokacyjny ma przekazać Albrecht Kapitule. Pozostałe 6,5 łana były zadłużone i zostały przed 4 latami za 24 marki zajęte przez Kapitułę, to samo dotyczy łanów sołeckich i karczmy. Te zadłużone łany były przedtem obsadzone przez chłopów: Olbrecht Jokil i Michel Merun, po 2 łany, i Lorenz Popose 1,5 łana. Teraz leżą te łany odłogiem.

W dniu 9.02.1479 r. administrator komornictwa Christian Tapiau kupuje od dostojnych mężczyzn Zacharias Wolff z Swoben i Jeniche z Claukendorff:
a) 2 łany, które są obsadzone gospodarzem Matz Henike, każdy łan po 26 marek.
b) 2,5 łana leżące odłogiem za dodatkowe 33 marki. Z tej sumy 85 marek, 40 musi być zapłacone natychmiast, a reszta – 45 marek w bieżącym roku w dniu 11.11. Dostojnymi świadkami są: Girsig z Mertensdorff i Beith z Claukendorff. W rejestrze administratora jest potwierdzonych kilka wpłat.

Cały dotychczasowy majątek szlachecki przeszedł na własność Kapituły. W roku 1484 Peter Dase przejmuje 1,5 łana od Austena Packmora, czynsz od 1485 r. W roku 1497 Urban, syn Urbana obsadza 2 łany Pawła, inwentarz: 3 konie, 1 źrebak i 2 krowy oraz 1 łan, który przedtem posiadał Georg Littau, czynsz od 1500 r. 1,5 łana tego Georga obsadza Bartolomis Welau, inwentarz: 2 konie, 1 krowa i 2 świnie, czynsz od roku 1501. Rok 1498, rok przedtem zbiegły Georg Littau, został schytany i wtrącony do lochu. Zobowiązuje się on do zapłaty po 7,5 marki w 3 ratach ad locandos ipsos mansos, poręcza Gabriel i jego stryj Ihan Littau z Patryk. Gdy stodoła Georga zawaliła się, Merten Grezeling otrzymuje słomę do jej pokrycia. 1,5 łana, które opuszcza Bartolomes Welau, przejmuje Andrzej Polen (Polak) wraz z inwentarzem, czynsz od 1503 roku. W roku 1500 zanotowano, że 4 łany leżą odłogiem. 14.10.1500 Nickel Steinberg obsadza 1 łan, czynsz od 1506 r. W roku 1501 Jorge Gretzil przejmuje 2 łany, z tych 3 łanów, które do tej pory posiadał Kirstan, z inwentarzem: 3 konie i 3 krowy, czynsz od 1504 r.; pozostałe 3 łany będą dzierżawione. Jorghe zobowiązany jest wobec Barbary, wdowy po Grose Matz, wysiewać przez 3 lata, 0,25 (?) lnu. We wsi pozostają 4 opustoszałe łany. Rok 1502, z tych 2,5 łanów, które dotychczas posiadał zubożały Groskop, Jorgh Pippelke przejmuje 2 łany wraz z inwentarzem: 3 krowy i 3 konie, czynsz od 1506 r. Pozostałość przejmuje Peter Glande, czynsz od 1504 r. Rok 1503, Cleyn Hans przejmuje 1,5 łana otrzymując zapomogę, 1 konia i 2 dobrych marek, czynsz od 1506 r. Rok 1505, Andris przejmuje 2,5 łana z 4-letnią wolnizną.

Tych poniższych 3 zapisów dokonał Mikołaj Kopernik, który w tych dniach był osobiście w Wójtowie, dokonując zmian majątkowych:
11.12.1516 r., Wójtowo. Jan Bodner objął 3 łany, które mu sprzedał Andrzej Daumschen. Jerzy Knobel posiada 2 łany po spalonym gospodarstwie i w międzyczasie zmarłym Piotrze Glande nabył 1 łan dodatkowo. Grzegorz jest kuratorem i bratem nieletniego Piotra i obiecuje go zadowolić, jak będzie dorosły. Działo się to 11 grudnia Roku Pańskiego 1517 r., lokacja łanów opuszczonych dokonana przeze mnie, Mikołaja Kopernika, kanonika i administratora.
26.03.1516 r., Wójtowo. Jorge Woyteck objął 2,5 łana po Piotrze Glande, który ongiś zrujnował i spalił swoje gospodarstwo. Zapłaci czynsz najbliższy. Działo się to 26 marca.
30.03.1517 r., Wójtowo. Marcin (Martzin) do swoich posiadanych 2 łanów przejmuje jeszcze 1 łan, który mu sprzedał stary Urban, stary z wieku i nazwiska. Temu Urbanowi i żonie jego jako zgrzybiałym, bez synów, przyznałem wolność. Działo się to przed 30 marca. (Wolność tzn. opuścić gospodarstwo mógł chłop tylko wtedy, gdy znalazł następcę. Kopernik jak widać był pod tym względem bardzo ludzki.)
12.07.1517. Wójtowo. Jakob ze Skajbot, który kupił tamże wolne łany za zezwoleniem pana prepozyta (mowa o Krzysztofie von Suchten – proboszczu Kapituły Warmińskiej, który w latach 1513-1516 był administratorem przed Kopernikiem). W ubiegłym roku 1516 mając tu 2 łany, sprzedał je za moją zgodą Lorenzowi, bratu sołtysa. Działo się to 12 lipca.

W dniu 22.01.1514 r. Kapituła nadaje nowy przywilej lokacyjny, w którym postanawia, że z tych 45 łanów sołtys Peter Kratel otrzymuje 1,5 łana. Z łanów czynszowych jest do zapłacenia co roku 0,5 marki od łana. Z tego czynszu 3/4 otrzymuje zarząd pogrzebowy oraz magister, który odmawia godzinki w katedrze. Rok 1521, Hans Uff, który posiada 2,5 łana, a chciałby je przekazać synowi, otrzyma inne 2,5 łana po zmarłym Brosiusu, które obiecał zagospodarować. Jako zapomogę otrzymał 1 krowę, 4 świnie i 1/2 pola obsianego żytem. Czynsz płaci tak, jak inni poszkodowani. Wpisano 12.08.1521 r. W dniu 12.03.1526 r.
Simon Glen otrzymuje 3 opustoszałe łany z 3-letnią wolnizną. Jako zapomogę otrzymuje on 1 krowę, 2 korce żyta i 4 korce owsa. Poręczają: sołtys Peter Kratil i Kaspar Matern. Rok 1532, Martin Merzke obsadza 2 opustoszałe łany, które należały do Nicolai Cleberg, a obsadzone były przez Hansa Wolge. Otrzymuje on 3-letnią wolniznę oraz zapomogę, poręcza powyższy sołtys. Gospodarze posiadają w latach 1584-1600 43,5 łana i płacą za każdy po 1 marce rocznie. Pod koniec XVI wieku urzędujący sołtys Peter Lignau został z przyczyn moralnych usunięty z tego stanowiska. W roku 1656 wieś posiadała 44,5 łana z 15 gospodarzami, którzy mieli do odstawienia czynsz: po 1 korcu pszenicy i innego zboża, 66 kur, 18 gęsi, a do zapłaty 9 groszy. Wznowienie lokacji nastąpiło w latach 1653-1660, na prośbę sołtysa Clemensa Brauna.

W roku 1895 założono tu agenturę pocztową, a w dniu 25.07.1911 r. doszedł zakład telegraficzny i publiczny telefon. W roku 1931 doszedł jeszcze jeden telefon, u gospodarza Jagalskiego. W 1939 r. agenturę pocztową zmieniono na urząd pocztowy II klasy.
W czasie I wojny światowej Rosjanie spalili gospodarstwo wdowy Schlomm. Jako świadek tego zdarzenia był August Gulowski przesłuchiwany w sądzie w Barczewie.
Królewski Urząd Sądowy dnia 23.12.1914 r.
Barczewo, Radca Urzędu Sądowego Meyer
Dokonano przesłuchania świadka, jak następuje:
Zagrodnik August Gulowski z Wójtowa.
W dniu 31 sierpnia orałem w ogrodzie zagrodnickim u wdowy Schlomm w Wójtowie. Około południa z kierunku Barczewka wkraczało do Wójtowa wojsko rosyjskie. Przy tej drodze leżało gospodarstwo Schlommów. Widziałem jak jeden z tych żołnierzy rzucił na szopę wdowy Schlomm jakiś przedmiot, którego nie mogłem określić. Szopa natychmiast stanęła w płomieniach. Pożar przerzucił się również na dom mieszkalny. Oba budynki zostały aż do fundamentów doszczętnie spalone. Z budynku mieszkalnego mogliśmy uratować tylko kilka przedmiotów. W szopie znajdował się mój koń, który padł ofiarą pożaru. Podpis August Gulowski

W roku 1825 nauczycielem był Johann Orgassa, ur. 1763 r. Zawód ten wykonywał już od roku 1789. Przedtem był krawcem, uczył się w Tuławkach. W szkole zameldowanych było 36 dzieci, a obecnych tylko 5, frekwencja zła. Po niemiecku nie uczą się i nie mówią. Religii uczą się z polskiego katechizmu. Czytają tylko po polsku, ale źle. Nie uczą się pisać, rachować, śpiewać ani niczego innego. W roku 1854 uczęszczało do szkoły 18 chłopców i 17 dziewcząt z Wójtowa oraz po 6 chłopców i dziewcząt z Bogdan i 3 chłopców i 1 dziewczyna z Tracka. W roku 1927 nauczycielem był Jabłonka. Później szkoła była 2-klasowa. Nauczycielami byli: Paweł Berger, Paweł Schwarzer, Paweł Górski, Paweł Skibowski.

Dokładnie po 600-letniej nieprzerwanej przynależności Wójtowa do parafii Klebark Wielki, JE ks. arcybiskup Edmund Piszcz, dekretem z maja 1999, wyłączył Wójtowo z parafii Klebark Wielki z dniem 1.07.1999 r., tworząc własną parafię pod wezwaniem Najświętszej Marii Panny Królowej Męczenników, należącej do dekanatu Barczewo. Odpust przypada w dniu 13 czerwca.

W pierwszym roku istnienia parafii Msze św. i nabożeństwa odprawiane były w dawnej szkole, na końcu wsi w drodze do Kaplityn. Latem 2000 r. Adam Marel ofiarował elementy drewniane, z których powstała pierwsza kaplica do nabożeństw. Od początku funkcjonowania parafii, przewodniczącą Rady Parafialnej była i jest mgr Teresa Jezierska-Rogowska. Plac, który przewidziany był pod budowę kościoła poświęcił w dniu 18.07.1999 dziekan z Barczewa, ks. kanonik Marek Paszkowski. Budowę kościoła rozpoczęto we wrześniu 2000 r. Kierownikiem budowy kościoła był i jest mgr inż. Ireneusz Tarasiewicz, który z sercem i poświęceniem troszczy się o jej kontynuację i szczęśliwe zakończenie.

Pierwsze nabożeństwo w tym kościele odprawione zostało w Pasterkę 24.12.2005 r. o godz. 22.00. Krzyż nad kościołem, którego fundatorem był Janusz Skowroński, właściciel firmy „TEWES-BIS”, poświęcił w dniu 20.09.2006 JE ks. arcybiskup metropolita warmiński Wojciech Ziemba. Kościół budowali i budują parafianie w czasie wolnym od pracy zawodowej. Podczas nabożeństw parafia używa własnego śpiewnika, który cieszy się tak wielkim powodzeniem, że wydano drugi nakład.

Obecnie parafia liczy około 900 wiernych.
Pierwszym proboszczem tej parafii został ks. mgr Krzysztof Bumbul, ur. 4.03.1969 r. w Dobrym Mieście. Uczęszczał do Szkoły Podstawowej nr 3 w Olsztynie, a następnie w latach 1984-1989 do Technikum Kolejowego, kończąc go maturą i tytułem „technik kolejowy”. W latach 1989-1995 był alumnem Wyższego Seminarium Duchownego „Hosianum” w Olsztynie. Tytuł magistra z teologii biblijnej zdobył na Papieskiej Akademii w Krakowie. W międzyczasie w latach 1987-1989 był organistą w parafii Serca Jezusowego w Olsztynie. Święcenia kapłańskie przyjął w dniu 27.05.1995 r. z rąk JE ks. arcybiskupa Edmunda Piszcza. W okresie od 1.07.1995 do 30.06.1999 był wikariuszem w parafii Św. Apostołów Piotra i Pawła w Lidzbarku Warmińskim. Od 1.07.1999 jest proboszczem parafii Wójtowo.

Historia napisana przez Georga Kellmanna „Historia parafii Klebark Wielki jej wiosek i okolic”

Historia zamieszczona na stronie wojtowo.pl za zgodą księdza Henryka Błaszczyka proboszcza Parafii Znalezienia Krzyża Świętego i Narodzenia Najświętszej Maryi Panny w Klebarku Wielkim, udzieloną 10 sierpnia 2017 r.