W pobliżu wsi znajduje się cmentarzysko z okresu brązu, co świadczy o dość wczesnym osadnictwie w tym miejscu. Wieś założona w 1399 r. na miejscu dawnej osady Prusów. Pierwotnie była osadą bartników (w 1450 było tu kilku bartników, m.in o imieniu ''Lusuta''), jeszcze w 1785 r. na 19 chłopów 10 było bartnikami. W 1496 r. sołtysem we wsi był Maciej Molewski.
Stare Kiejkuty są też siedzibą formalnie jednostki wojskowej 2669, którą jesienią [[1971]] przekształcono w będący tajną nazwą [[Ośrodek Kształcenia Kadr Wywiadu]] (JWpodlegający 2669)pod [[Departament I MSW]] PRL, formalnie część [[Nadwiślańskie Jednostki Wojskowe|Nadwiślańskich Jednostek Wojskowych]]. Obecnie ''Ośrodek Szkolenia [[Agencja Wywiadu|Agencji Wywiadu]]''. Niedaleko znajduje się [[Port lotniczy Szczytno-Szymany|lotnisko w Szymanach]] (od połowy lat 90 XX w. lotnisko cywilne), które zapewnia łatwy dostęp do jednostki. Na przełomie [[2005]]/[[2006]] r. o wsi stało się głośno w całej Polsce za sprawą właśnie ww. jednostki. Według raportu Rady Europy<ref>Oficjalny raport końcowy ze śledztwa Dicka Marty'ego dla [[Rada Europy|Rady Europy]], [http://assembly.coe.int/Main.asp?Link=/CommitteeDocs/2006/20060606_Ejdoc162006PartII-FINAL.htm] ([[HTML]]), [http://assembly.coe.int/Main.asp?Link=/CommitteeDocs/2006/20060606_Ejdoc162006PartII-FINAL.pdf] ([[PDF]])</ref><ref>[http://assembly.coe.int/Main.asp?link=/Documents/AdoptedText/ta07/EREC1801.htm Dokument przyjęty przez Zgromadzenie Parlamentarne Rady Europy]</ref> byli tu (świadomie<ref>''Investigator Says US Exported Torture Via Europe'', ''[[Deutsche Welle|DW-World]], 24 stycznia 2006, [http://www.dw-world.de/dw/article/0,,1867838,00.html?maca=en-rss-en-all-1124-rdf]</ref>, nielegalnie wobec przyjętych przez Polskę przepisów międzynarodowych) przewożeni i przesłuchiwani przez [[CIA]] więźniowie.
