První zmínka se o vesnici objevuje již v roce 1299 ve spojitosti se jmény bratří Ludíka, Konráda a Herborda z Čehovic.

V roce 1358 pak Jan a Bareš z Čehovic zaměnili Čehovice za statky v Stachové a tím patřila vesnice k šternberskému hradu. Ve 14. a 15. st. se objevují v listinách různé názvy pro tuto obec - Czichowicz, Czyhowicz, Čihovice.

V roce 1397 umírá Petr ze Šternberka jako bezdětný a Čehovice tak připadají dědictvím rodu z Kravař a poté v roce 1490 prodejem přechází do rukou Ctibora Tovačovského. V roce 1503 kupuje panství tovačovské, Čehovice a mlýn Vilém z Pernštejna, od těch dob sdílely Čehovice osud spolu s tovačovským panstvím až do roku 1848.

V obecním archivu se zachovala pergamenová listina z r. 1503 na dvůr vydaná Janem ze Schellenberka a Johankou z Krajku, v roce 1577 Čehovicím Vratislav z Pemštejna propůjčil erb a znamení na pečeť, jen málo obcí se může pyšnit takovými dokumenty.

Brzy po začátku třicetileté války byly Čehovice vypáleny a zničeny vojsky Bethlena Gábora (1621-1623) a znovu od základu vystavěny, ale o 1 km níže, blíž k řece Vřesůvce.

Na původním místě, kde vesnice stála, je dosud na památku kaplička sv. Prokopa.

Pouze tři obce prostějovského okresu mohou v současnosti doložit, že vlastní originály privilegií udělujících znak nebo pečeť. Tyto historické dokumenty jsou dnes velkou vzácností a dokonce ne každé město se jimi může pochlubit. Čehovice tuto výsadu mají. Podle dochované listiny z roku 1577, kterou vydal Vratislav z Pernštejna, jim patří erb žlutomodré barvy, rozdělený na čtyři části. Erbu vévodí část useknuté zubří hlavy, na níž je vidět houžev protažená skrze nozdry. Tento symbol je vlastní rodu Pernštejnů a opakuje se například v kamenných reliéfech na městské bráně v Pardubicích a na bráně hradu Helfštýna, kam byl vyryt už kolem roku 1480.

Čehovice svůj znak po staletí uchovávaly a oficiálně používaly. Svědčí o tom úřední listiny z doby rakousko-uherské monarchie i z tzv. první republiky, opatřené razítkem, na němž je vypodoben starobylý znak.