Od XVII wieku w Kostomłotach istniała parafialna cerkiew unicka. W 1875 miejscowi unici 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 (katolicy łacińscy, czyli rzymscy, a także uniccy i prawosławni).
W 1945 niepolska 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 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 na terenie wsi działalność duszpasterską prowadzi Polski Autokefaliczny Kościół Prawosławny. W 2003 we wsi został założony męski monaster oraz reaktywowano parafię prawosławną. Z Dobrowody do Kostomłotów przeniesiono drewnianą cerkiew, służącą obecnie zarówno monasterowi, jak i parafii, choć mieszkańcy wsi są głównie katolikami.