Wieś o rodowodzie średniowiecznym. Od 1412 roku własność zakonu augustianów z Brześcia Litewskiego, od XVI wieku w posiadaniu rodziny Sapiehów z Kodnia. W XIX wieku w miejscowość należała do różnych rodów ziemiańskich. Jednym z właścicieli majątku ziemskiego w Kostomłotach w tym czasie był publicysta Tygodnika Ilustrowanego, Józef Łoski.
Od XVII wieku w Kostomłotach istniała parafia greckokatolicka. W 1875 wierni uniccy zostali administracyjnie podporządkowani Rosyjskiej Cerkwi Prawosławnej. W 1927 obok parafii prawosławnej powstała katolicka parafia obrządku bizantyjsko-słowiańskiego. W okresie międzywojennym w miejscowości dochodziło do wielu konfliktów na tle wyznaniowym.
W 1945 r. znaczna część mieszkańców wsi została wysiedlona na Mazury w ramach Akcji Wisła. Ich miejsce zajęli Polscy wysiedleńcy z Kresów Wschodnich i migranci.
Od lat 60. XX wieku wieś jest jedynym w Polsce ośrodkiem prowadzenia duszpasterstwa katolickiego w obrządku bizantyjsko-słowiańskim. W 1985 roku powstał w Kostomłotach dom zakonny Małych Sióstr Jezusa. W latach 1998-2007 istniał dom zakonny marianów. Od początku XXI wieku obserwowana jest również wzmożona działalność Polskiego Autokefalicznego Kościoła Prawosławnego. W 2003 roku we wsi został założony męski monaster i parafia prawosławna. Zbudowano też cerkiew, służącą zarówno monasterowi, jak i parafii.
Włócząc się po Polsce (oczywiście rowerem), zaliczyłem też wizytę w Kostomłotach. Wieś robiła na mnie wrażenie opustoszałej, wymarłej. Przejeżdżając rowerem nie spotkałem żywej duszy, jedynie z domostw dobiegały śpiewy modlitewne. Nie można było nawiązać kontaktu z „żywym człowiekiem”. Jedynie żołnierze WOP czujni, staranni, legitymowali mnie kilka razy, gdyż wieś leży w bezpośredniej bliskości pasa drogi granicznej, w strefie nadgranicznej.
Uroki polskiego orientu. Artykuł opracowany solidnie, brak jednak dokumentacji fotograficznej. Ja jej nie posiadam.
