Podole Małe od co najmniej XV wieku było lennem środkowopomorskiego rodu szlacheckiego von Zitzewitzów. W latach 1717–1766 połowa wsi należała również do rodziny von Miltitz. W 1931 miejscowość przeszła w posiadanie Niemieckiej Spółki Kolonialnej GmbH z Białogardu. 1 września 1945 we wsi zamieszkali pierwsi przesiedleńcy z Kresów Wschodnich. 6 listopada 1946 ruszył pierwszy transport ludności niemieckiej za Odrę. Od 5 października 1954 do 31 grudnia 1959 istniała gromada Podole Małe.
Do obiektów objętych rejestrem zabytków województwa pomorskiego z terenu wsi należą grodzisko wczesnośredniowieczne, datowane na VII-VIII/IX wiek, i park pałacowy, założony w drugiej połowie XIX wieku. Do ewidencji zabytków wpisana jest również murowana kuźnia z początku XIX wieku.
Geografia Położenie Podole Małe według regionalizacji fizycznogeograficznej leży na obszarze megaregionu Pozaalpejska Europa Środkowa, prowincji Nizina Środkowoeuropejska, podprowincji Pojezierza Południowobałtyckie, w obrębie dwóch makroregionów – Pobrzeża Koszalińskiego (313.4) i Pojezierza Zachodniopomorskiego (314.4) – oraz odpowiednio dwóch mezoregionów Wysoczyzny Damnickiej (313.44) i Wysoczyzny Polanowskiej (314.46). Według regionalizacji Jerzego Kondrackiego obszar wsi w całości znajdował się w granicach Wysoczyzny Polanowskiej.