Místo bylo osídleno již v pravěku. Při archeologických vykopávkách byly nalezeny v Kosteleckém lese mohyly s lužickou keramikou, žárové hroby s amforami, bronzová jehlice a náramky. Není však známo, kdy obec vznikla a kdo ji založil. První písemná zmínka pochází z roku 1131 z latinsky psané listiny olomouckého biskupa Jindřicha Zdíka. Od té doby se na kosteleckém panství vystřídala řada pánů a šlechtických rodů. Posledním vlastníkem byl až do třicátých let minulého století hraběcí rod Vrbnů z Holešova. Od roku 1997 má obec obecní znak a prapor. Překřížený klíč a meč ve znaku jsou symboly patronů místního kostela, který je zasvěcen sv. Petru a Pavlovi. Hradební zeď a cimbuří symbolizují tvrz, která ve 13. století stála nad obcí na Hradisku. Červená barva štítu vyjadřuje mučednickou smrt obou patronů a byla převládající barvou v erbech rodů, jimž obec v minulosti patřila, zejména Prusinovských z Víckova, Lobkoviců, Rottalů a Vrbnů. Z těchto rodů je třeba připomenout vnučku Františka Antonína hraběte z Rottalu hraběnku Marii Barboru provdanou za hraběte Erdëdyho, která jako jediná paní na holešovském panství založila v roce 1780 na katastru obce Kostelec osadu , kterou nazvala podle svého syna Karlovice a osídlila ji dvaceti svými poddanými z Kostelce.