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.