V obci se nalézá pískovcová raně románská křtiltelnice, která patří k nejstarším evidovaným památkám hmotné kultury na Prostějovsku, a dokládá tak starobylost křesťanského období Stařechovic.
O minulosti Stařechovic vypravují nejstarší písemné zprávy teprve z poloviny 14. století, pocházející z pera jedné z větví pánů z Kunštátu, vlastníků zdejší tvrze a vsi. Tvrz se nalézala na jihozápadním okraji vesnice. Vnější ochranu tvrze tvořil okružní příkop, pravděpodobně napájený z blízkého potoka. Ten je dnes zahrnut a rovněž zredukované koryto je dnes vedeno poněkud jinou trasou než v minulosti. Sotva znatelnou připomínkou tvrze je malý pahorek (17x17 m) za domem čp. 10, z něhož je část odtěžena. O šířce příkopu, která byla asi 15 m, vypovídá jen prosednutí terénu na vychodě a severozápadě. Z počátku 15. století se ve Stařechovicích uchovala památka mimořádné kulturní a historické hodnoty - gotická Madona.
Za válek husitských se stal majitelem Stařechovic Hynek z Valdštejna, později Jiří z Kravař a Václav z Boskovic. Ovdovělá Kunka z Boskovic se svým synem Ladislavem z Boskovic vydala pro obyvatele Stařechovic dne 6. února 1499 v Moravské Třebové odúmrť - listinu, kterou dává všem obyvatelům Stařechovic svobodu při rozhodování o dědicích jejich majetku. Ladislav z Boskovic vesnici Stařechovice s pustou tvrzí prodal Vilémovi z Perštejna. Uprostřed bouřlivých událostí třicetileté války Stařechovicemi a okolním krajem procházela císařská i cizí vojska. Z roku 1643 máme dost smutných zpráv o řádění švédské soldatesky, která drancovala celý kraj. Podle farního zápisu měly Stařechovice od roku 1790 vlastní školu. Roku 1880 koupila obec hospodu Na pindólé a přestavěla ji vlastním nákladem na školu. Válečné události husitských válek, války třicetileté, války Marie Terezie proti Prusům, i pochody napoleonských vojsk byla období nesmírných útrap a rabování. V roce 1910 žilo v obci 415 obyvatel, přišla však 1. sv. válka s hladomorem v r. 1917. Padlé připomínají památníky obětem ve Stařechovicích i ve Služíně. V posledních letech 19. století nastal značný pokrok v zemědělské výrobě, což vedlo k založení Rolnického mlékařského družstva pro Stařechovice a okolí (jedno z prvních na Prostějovsku). Po vzniku svobodného Československa, počátkem 20. let, došlo k parcelaci velkostatkářské půdy. Poklidný život obce narušily stísněné hospodářské poměry za hospodářské krize v r. 1929. V témže roce bylo dokončeno scelování pozemků a jejich odvodnění, čímž se obec značně zadlužila. V r.1930 byla do obce zavedena elektřina. Dne 15. března 1939 projela obcí autokolona německé armády, začaly roky fašistické okupace. Osvobození se vesnice dočkala až 9. května 1945. Novodobé dějiny poznamenala období 2. sv. války a čtyřicetiletého budování socialismu, která změnila zvláště architekturu vesnice, ze které se vytrácí charakteristický architektonický detail a tradiční tvarosloví.
- Brus (přírodní památka) v katastrálním území Služín
- Hřbitov
- Památník obětem 1. světové války
- Památník T. G. Masaryka
- kaplička sv. Martina
- kostel Narození Panny Marie