Přestavlky vznikly asi ve stejném období jako většina okolních obcí. První písemná zmínka o nich je z roku 1358, avšak v seznamu památek okresu Olomouc je uveden rok 1275.
Zpočátku byly rozděleny mezi několik vladyků. Majitelé se střídali. V roce 1592 měly Přestavlky tvrz, poplužní dvůr a snad i pivovar.
Od druhé třetiny 17. století měla obec stejnou vrchnost jako Hostkovice. V roce 1636 připadla olomouckým kanovníkům a v letech 1651-1773 náležela jezuitské koleji v Olomouci. Po zrušení jezuitského řádu v roce 1773 připadly Přestavlky vrchnosti z Rokytnice. Do roku 1848 již k dalším změnám nedošlo.
Ze 17. - 19. století jsou známy následující údaje:

• 1657: V obci bylo 10 zahradníků, 2 opuštěné chalupy a panský dvůr.

• 1780 (po 123 letech): Obec měla pouze 7 usedlostí.

• 1837 (po 57 letech): V Přestavlkách žilo 221 obyvatel ve 30 domech. V uvedeném mezidobí bylo asi provedeno rozdělení pozemků přestavlckého dvora novým usedlíkům. (Přestavlky kolem roku 1837 byly relativně velkou obcí, např. Vacanovice tehdy měly jen 126 obyvatel, Lipňany 176 obyvatel.)

V následujícím stoletém období se počet obyvatel příliš neměnil. V roce 1930 bylo napočítáno 223 obyvatel. Stěhování mladých manželů s rodinami do měst nastalo po 2.světové válce, takže v roce 1983 již měly Přestavlky pouze 103 obyvatel.
Po roce 1848 se Přestavlky staly součástí politického okresu Hranice, soudního okresu Lipník nad Bečvou, což trvalo do roku 1877. Od té doby přísluší k okresu Olomouc.
V roce 1960 došlo k sloučení Přestavlk s Hostkovicemi, o několik roků později ještě navíc se Suchonicemi a v roce 1974 pak vše připadlo k Tršicím.
Obec je součástí Penčické farnosti. Zemřelí odpočívají na hřbitově u kostela v Suchonicích.
Děti dříve chodily do školy v Suchonicích a do měšťanské školy v Tršicích. Nyní dojíždějí do Tršic již od první třídy.
Obvodního lékaře měli přestavlčtí občané vždy v Tršicích.

Seznam snadno dostupných písemností a dokumentů:

• Článek K.Orla z Tršic o historii Přestavlk byl uveřejněn v Tršickém měsíčníku č.12 z roku 1992
  

• Úvod k seznamu přestavlckých archiválií, v němž je popsána historie obce. Nachází se v příslušném dílu "Skupinového inventáře archívu obcí". Lze jej prostudovat ve Státním okresním archívu v Olomouci.
  

• Pamětní kniha Raimunda Koutného z Hostkovic. Obsahuje mimo jiné popis tragických událostí, které se staly v Přestavlkách na sklonku minulé války. Je uložena v Olomouckém archívu, v oddílu obce Hostkovic.
  

• Archívní dokumenty: Ve Státním okresním archívu v Olomouci jsou uloženy písemnosti, předané bývalým MNV v Přestavlkách v roce 1955. Jsou z období let 1830-1945. Celkem je tam uloženo 45 dokumentů z Přestavlk.

Zmínky a pravděpodobně i rozsáhlejší sdělení o Přestavlkách se nacházejí v mnoha knihách i časopiseckých článcích. Jejich vyhledání může usnadnit např. seznam použité literatury, kterou použil Ing. Vladimír Černík z Lipňan při shromažďováním informací o historii své obce. Seznam obsahuje:

• Historický místopis střední a severní Moravy (Norbert Černý, Přerov, 1942)

• Vlastivěda moravská II-místopis, Olomoucký okres (Dostál, Říkovský, Brno, 1935)

• Dějiny obce Vacanovice (Václav Nešpor)

• Předhusitské Čechy (Zdeněk Fiala, Svoboda Praha 1968)

• Historický místopis Moravy a Slezska 1848-1960 (Lad.Hosák,Ostrava 1967)

• Historický místopis Moravy a Slezska 1848-1960 (Jos. Bartoň a kol., Ostrava 1972)

• Historický místopis stř. a sev. Moravy, okres Olomouc (Lad. Hosák, Olomouc 1959)

• Lánové rejstříky olomouckého kraje z let 1675-1678 (Olomouc 1994)

• Vlastivěda moravská, sv. 6 - Josef Válka: Morava reformace, renesance a baroka

• Moravští sedláci 1848-1904 (František Obrtel)

• Nejstarším je Parcelní protokol z let 1830-1831

• O lesním hospodářství obce a obecní honitbě jsou k dispozici dokumenty z období 1881-1931

• Několik desítek domovských listů, vystavených v různých obcích (pravděpodobně občanům, kteří se do Přestavlk přistěhovali), je uloženo v samostatné složce. Mají mnohdy odlišný obsah i úpravu.

• Zachovalo se také povolení k provozování obecního kamenolomu z roku 1902

• Velmi podrobné informace o nedávné minulosti obsahují zajisté obecní účetní knihy z let 1914 -1945.

• Úplný seznam přestavlckých archiválií se nachází ve SOA Olomouc, ve "Skupinovém inventáři archívu obcí".

• Obecní kronika se v archívu nenachází. V dávnějších dobách však možná byla vedena.

Dostupné prameny se v podrobném popisu událostí částečně odlišují, v tomto případě doslova cituji z díla : Jan Cekl - Kraj, kterým táhla válka. Děje, události a dokumenty z let 1939-1945, II. doplněné vydáni, Olomouc 1946

Naše obec vytrpěla za nacistické okupace opravdu velmi mnoho. Zaplatila daň krve měrou opravdu značnou a přinesla na oltář vlasti velké oběti. Dne 19.července 1939 odešel z domova 18letý Miroslav Tuška, aby se přes Polsko dostal do Ruska, jako dobrovolník zahraničního odboje. Z tohoto důvodu byli zatčeni a odvezeni gestapem jeho rodiče Josef a Anna Tuškovi a sice 17.9.1942. Jmenovaní byli koncentrováni nejdříve v Olomouci a pak převezeni do Svatobořic, odkud byli 19.1.1943 propuštěni. Dne 17.července 1942 byla zatčena sl. Pavla Chrobáková a to v Olomouci v nemocnici, kde byla na léčení. Proč byla zatčena, dodnes nikdo neví. 13.prosince 1942 zemřela v Osvěnčimi.
V roce 1943 počal u nás odbojovou činnost p.Josef Tuška po svém návratu ze Svatobořic, spolu p.Jaroslavem Tuškou, hostinským, a p.Frant.Mačákem, roln.synkem. Podrobnosti jejich činnosti nám nejsou známy, jelikož všichni jmenovaní nežijí.
Začátkem dubna 1945 přišla do naší obce skupina partyzánů por.Juraje, která se zdržovala v naší obci a odtud činila výpady. Koncem dubna skupina partyzánů odešla a v obci zůstali jen dva ruští parašutisté. V noci z 30.4. na 1.5.1945 napadla naši obec skupina SS a Vlasovců, vedená gestapáky. Po zapálení hostince p.Jaroslava Tušky, roln. usedlosti p.Jos. Tušky, rol. p. Jaroslava Mačáka, rol. pí. Pavly Teimerové, děl. domku p.Ludvíka Houšťavy a Jana Machovíka, počala skupina po obci loupit a vraždit. V onu osudnou noc měl právě hostinský Jar.Tuška hostinec uzavřen a v kuchyni byli přítomni p.Lud. Frajt z Olomouce-Černovíra spolu s p.Sitou, dr. Tuškou ze Suchonic a šoférem, rovněž tam byl 1 parašutista. Co se tam všechno odehrálo, nikdo neví, jelikož nikdo nemohl ven, poněvadž bylo po každém stříleno. Ráno po 6.hodině, když horda vrahů odjela, byly na křižovatce u hostince nalezeny mrtvoly: p.Jar Tušky, hostinského, p.Jar.Mačáka, rolníka, bratří Jana a Frant. Mačákových, roln.synů, p.Lud. Frajta z Olomouce-Černovíra, p.Sity z Olomouce a p.Frajta z Přerova. Panu Josefu Tuškovi a jeho synu, které, jak z dotazů Vlasovců bylo zřejmo, hledali, se podařilo uprchnouti.
Osud však tomu asi chtěl, že p. Josef Tuška, vůdce celého ilegálního hnutí v naší obci, musel svůj život skončit. Dne 8.května 1945 při příchodu Rudé armády dal se do jejích služeb jako spojka a když je vedl proti hnízdu německých kulometů, byl zastřelen. Tak tragicky skončil tento hrdina se svými spolupracovníky, aniž mohl užíti výsledků svobody, pro jejiž dosažení tolik obětoval.

Ve Státním seznamu nemovitých kulturních památek je pod číslem 1909 evidován Památník umučeným v Přestavlkách. Nese tyto nápisy:
Umučeným 1. V. 1945
Mačák František, nar. 10. 7. 1913
Mačák Jan, nar. 10. 2. 1905
Mačák Jaroslav, nar. 10. 8. 1908
Tuška Jaroslav, nar. 14. 3. 1896
Frajt Ludvík, nar. 23. 9. 1903
Sitta Antonín, nar 7. 11. 1910
Sklenář Jaroslav, nar. 26. 11. 1925
Tuška Josef, 1896, raněn, zemř. 8. 5. 1945
Chrobaková Pavla, 1920, zemř. v Osvěčimi
Klich ……., 1915, zemř. 12.6.1943 v Mauthausenu (na samostatné desce)
Věčná paměť!

V seznamu nemovitých kulturních památek místního a regionálního významu okresu Olomouc, který vydal Okresní památkový ústav v Olomouci v roce 1999, jsou z Přestavlk zapsány:

• kaple sv. Karla Boromejského, na návsi, parc. č. 29
• kamenný kříž, naproti č. p. 38, parc. č. 100/4
• pomník obětem I.světové války, na návsi, parc. č. 151/1

Na pomníku obětí I.světové války jsou uvedena tato jména:
Hudec Jan 1894-1916
Jurečka Raimund 1880-1918
Laštůvka Jindřich 1885-1916
Peřina František 1900-1918
Peřina Vít 1894-1917
Sehnal František 1869-1918
Smejkal František, legionář, 1894-1917
Svoboda František 1878-1916
Vyhlídal Bedřich 1897-1916
Zapletal Rudolf 1895-1915

Sídlila v budově, která byla jejím vlastnictvím a nyní náleží obci. Existovala po celé období I.republiky a zanikla kolem roku 1965. Sloužila také klientům z Hostkovic a Suchonic. Ztratila význam po likvidaci soukromých rolnických hospodářství.

Zdrojem obživy převážné většiny občanů Přestavlk bylo až do padesátých let samozřejmě zemědělství a také práce v lese. V meziválečném období však již řada občanů nalezla zaměstnání v Olomouci a jiných průmyslových střediscích, přestože přes Přestavlky autobus nejezdil. Občané museli na zastávku do Hostkovic, případně absolvovali celou cestu na pracoviště pěšky nebo na kole.
Až do II.světové války měla obec 2 obchody, jedno pohostinství a působil v ní také řezník. Jiných řemeslníků a živnostníků zde nebylo. Za kovářem se muselo dojíždět do Vacanovic nebo do Suchonic, koláři pak byli v Suchonicích a v Čechovicích.

Není příliš povzbudivý, především z důvodu nekvalitního povrchu místních komunikací po provedené kabelizaci telefonní sítě a také z vzhledem některých neudržovaných neobydlených nemovitostí.

V obci bývala prodejna Jednoty, která byla navrácena v restituci, v současné době obchod v obci není. Několik pokusů místních občanů o podnikání v této oblasti ztroskotalo a za nákupy se proto musí dojíždět do Vacanovic, Suchonic nebo Tršic.
V současné době je v provozu pohostinství, kadeřnictví a nová prodejna smíšeného zboží MIKRO, kde se prodávají, mimo běžného sortimentu, potraviny pro zdravou výživu.

Je i v dnešní době, kdy se celostátně snižuje dopravní obslužnost malých obcí, dostatečné.

V obci jsou dvě rekreační lokality - uzavřená chatová osada 13-ti zděnných chat, která vznikla na konci 70-tých let a mladší zahrádkářská kolonie se zahradními domky. Obě jsou využívány především občany z Olomouce. I když poloha obce a její umístění v blízkosti lesů k rekreačnímu využití vybízí, většímu rozmachu brání nedostatek infrastruktury a služeb. Plánované vybudování koupaliště se neuskutečnilo.

• Obecní cesty a jsou vyasfaltovány, i když povrch je v současnosti ve velmi špatném stavu. Oprava vozovek se plánuje až po vybudování plošné plynofikace obce.

• Rozvod elektřiny je nadzemní a dostačuje.

• V provozu je obecní rozhlas.

• V r.1996 byla provedena kompletní podzemní rekonstrukce telefonní sítě a její napojení na novou tršickou digitální ústřednu.

• Nově je rekonstruováno veřejné osvětlení.

• V r.1998 byla vybudována nová autobusová zastávka.

• Od 2.října 2001 je obec plynofikována.