Redostowo (Radostowo, Radoszów), niem. Retztow - Pierwsza wzmianka o wsi pochodzi z roku 1274. Pierwsze ślady ludności na tym terenie pochodzą z okresu kultury łużyckiej: znaleziono tutaj siekierkę brązową z tuleją oraz bransoletę. Nazwa osady – w 1618 r. wymienionej jako Redstow, w 1628 r. Listow, w 1780 r. Retzlow, w 1784 r. Retztow – pochodzi od słowiańskiego imienia Radost lub Radosta, będącego zdrobnieniem od Radosława. Eberhard Tietz genezy nazwy doszukiwał się w słowie „Rez” (żyto) lub „Red” (wilgotne miejsce). Polską postać nazwy – Redostowo – ustalił ks. Kozierowski już w 1934 r.

W średniowieczu wieś stanowiła własność rodu von Eberstein z Nowogardu. W źródłach pisanych występuje po raz pierwszy w 1317 r. W wyniku działów rodzinnych w 1569 r. Redostowo otrzymał Wolfgang von Eberstein z linii maszewskiej. Sporządzony wówczas rejestr wymieniał 8 łanów czynszowych, 1 łan kościelny, 4 chłopów, 4 zagrodników oraz karczmę. Ponieważ zamek w Maszewie popadał powoli w ruinę hrabia Wolfgang postanowił w 1576 r. wybudować nową siedzibę rodową koło Redostowa. Na północ od wioski, przy drodze do Węgorzy, wzniósł nad Stepnicą zameczek myśliwski, zwany potem Wilczą Twierdzą (Wolfsburg). Urządzono przy nim rozległy zwierzyniec posiadający nawet zwierzęta egzotyczne. Po śmierci Wolfganga w 1592 r. gospodarzem zamku został hrabia Stefan Henryk, który zasłynął jako wielki entuzjasta łowiectwa. Gdy jednak w 1603 r. sporządzono kolejny spis posiadłości Ebersteinów okazało się, iż w Redostowie należy do nich jedynie 1 łan kościelny.

Już w 1625 r. do objęcia hrabstwa Nowogard – Maszewo desygnowano księcia Ernesta Bogusława Croy. Po jego śmierci w 1684 r. wieś przeszła pod zarząd Urzędu Domeny Państwowej w Nowogardzie. Zameczek nad Stepnicą opustoszał i powoli obrócił się w ruinę. Na „Wzgórzu Zamkowym”(Schlossbrink) jeszcze dziś dojrzeć można pozostałości jego kamiennych murów.

W 1776 r. dokonano parcelacji tutejszego folwarku osadzając na jego ziemi 8 nowych chłopów. W 1784 r. mieszkał we wsi pastor, kościelny, 10 chłopów (wśród których był sołtys oraz karczmarz), podleśniczy posiadający zagrodę chłopską , chłop kościelny, 3 chałupników, pasterz oraz kowal. Cała osada składała się więc z 20 zagród, w tym dwóch spichlerzy chłopskich. W 1815 r. przeprowadzono w Redostowie uwłaszczenie chłopów. W końcu XIX w. naliczono tutaj 79 budynków, w tym 2 przemysłowe i 32 mieszkalne. Do 35 gospodarzy należało 398 ha ziemi (246 ha gruntów ornych, 125 ha łąk i pastwisk, 6,5 ha lasów). W 1872 r. wieś liczyła 264 mieszkańców, w tym 53 dzieci w wieku szkolnym. W 1939 r. liczba ludności spadła do 210, zaś liczba gospodarzy nie uległa zmianie i nadal było ich 35.

Najcenniejszym zabytkiem Redostowa jest prawdziwa perła architektury sakralnej – uroczy kościółek szachulcowy wzniesiony na przełomie XVII i XVIII wieku, najprawdopodobniej na miejscu starszej, średniowiecznej świątyni. Ryglowe ściany budowli posiadają piękne wykończenie snycerskie. Na uwagę zasługuje zwłaszcza ornament kostkowy i sznurowy na belce oczepowej.

Sto lat po zbudowaniu kościoła przy jego zachodnim szczycie wzniesiono, ponad 20 – metrową wieżę o spadzistych ścianach. Dzwonnica zwieńczona jest wysokim, smukłym hełmem w kształcie ostrosłupa, który pokryty był pierwotnie gontem.

Obok kościoła zachowała się romańska kropielnica o średnicy 62 cm ozdobiona sznurowatym zgrubieniem. Z 1500 r. pochodził srebrny kielich mszalny o wysokości 15 cm oraz późnogotycki tryptyk, którego resztki już w 1910 r. przeniesiono do wieży. W scenie głównej ołtarza ( o wymiarach 124 cm x 97 cm) przedstawiono św. Jerzego, św. Katarzynę oraz NMP, na klapach natomiast 12 apostołów. Z predelli zachował się jedynie fragment maswerków oraz aniołki o wysokości 12,5 cm . Około 1600 r. świątynia otrzymała nowe wyposażenie wnętrza utrzymane w duchu Renesansu. Przy zachodniej ścianie szczytowej wzniesiono emporę organową z bogatym wystrojem snycerskim, zaś przed ołtarzem ozdobiono barierkę. W 1608 r. fundowano dwa brązowe świeczniki ołtarzowe o wysokości 40 cm . Pierwszy podarował hrabia Henryk von Eberstein, drugi miejscowy wójt Jan Retzlaf. Trzeci świecznik, cynowy o wysokości 48 cm, pochodził z 1802 r. Na modlitwę wzywały wiernych dwa kościelne dzwony. Młodszy odlany został w 1623 r. przez gisera Karstede ze Stargardu. Młodszy o średnicy 40 cm zdobił napis wykonany niewyraźną gotycką minuskułą: „aue maria gracia plena”. Około 1900 r. zamurowano 6 małych okienek na ścianie wschodniej kościoła.

Do 1945 r. świątynia posiadała rangę kościoła parafialnego z filiami w Krzywicach i Gliwicach. Po wojnie poświęcono kościół pod wezwaniem Najświętszego Serca Pana Jezusa. Na ołtarzu zawieszono współczesny obraz przedstawiający św. Piotra oraz Pana Jezusa kroczącego po falach.

W marcu 1945 r. w rejonie Redostowa skoncentrowały się znaczne siły niemieckie broniące podejścia do Goleniowa. Obok wioski rozegrała się bitwa, w której niemieckie działa pancerne zniszczyły 7 rosyjskich czołgów 2 Armii Pancernej gwardii. Redostowo powróciło do Macierzy 7 marca 1945 r. W latach 1945 – 1954 wieś należała do gminy Węgorza, zaś w latach 1954 – 1975 do gromady Osina. W styczniu 1992 r. liczyła 155 mieszkańców.