História obce sa traduje od polovice 12. storočia, keď bolo osídlenie doliny dokončené. Pravdepodobne v tom období vznikla obec s dnešným názvom Kostolná Ves. Cirkevne jej bol pridelený ľavý breh rieky Nitrice (ľudový názov Belianka).
Prvá písomná zmienka o obci je z roku 1332.
Za čias Rakúsko- Uhorska sa obec volala Kišeď Ház.
Najstaršie jadro obce sa datuje od polovice 12. storočia v okolí katolíckeho kostola, ktorého prvá zmienka je z obdobia 14. storočia. Domy boli stavané do kruhu a tým vytvárali akúsi pomyslenú kruhovú pavučinu. Boli to hlavne rody: Babašteje, Barteje, Šimoreje, Cebákeje, Ďureje, Hanuseje, Hopkeje, Homoleje, Hopčekeje, Ignáceje, Kocáreje, Krajčeje, Kurajeje, Medereje, Pániseje, Púčikeje,Slošiareje a židovský majer Šimku. Mnohé s týchto rodov tu žijú dodnes v súčasnej podobe priezvísk.
V obci sa nachádza pôvodne gotický kostol Narodenia Panny Márie, ktorý bol upravovaný v rokoch 1515, 1742, 1773. Oprava kostola z roku 1933 nadobudla terajší architektonický vzhľad. V kostole sa zachovala drevená socha Panny Márie s Ježiškom z. r. 1490 – 1500 od neznámeho majstra.
V parku veľa kostola na podstavci z r. 1775 stojí socha sv. Jána Nepomuckého.
V obci Kostolná Ves sa narodil aj slovenský matematik Doc. RNDr. Ján Futák, CSc. (* 8. september 1939, Kostolná Ves – † 4. máj 1994, Žilina). V roku 1957 zmaturoval na JSŠ v Handlovej. Získal aprobáciu z matematiky a fyziky na VŠP v Bratislave. V roku 1963 bol asistentom matematiky na Pedagogickom inštitúte v Martine, odkiaľ 1. septembra 1964 prešiel na Vysokú školu dopravy s spojov v Žiline na Katedru matematiky. Účinne pomáhal študentom súťažiacim v matematickej olympiáde. V roku 1972 získal na Pedagogickej fakulte Univerzity Komenského v Bratislave vedeckú hodnosť CSc. a v roku 1983 bol menovaný docentom pre matematickú analýzu. Venoval obyčajným diferenciálnym rovniciam a ich asymptotickým a oscilatorickým vlastnostiam, rovniciam s posunutým argumentom ako aj systémom týchto rovníc. Zomrel v Žiline 4. mája 1994.
