Podstenice naj bi ime (tako slovensko kot nemško) dobile po legi v plitvi dolini blizu skalnate stene pod vrhom Roga. Vas je nastala dokaj pozno. V kočevskem urbarju iz leta 1574 se še ne omenja. Zato velja, da naj bi jo okoli leta 1580 ustanovila grofica Magdalena Blagajska in njen sin Jurij. Verjetno gre za eno od treh roških vasi, ki so bile s svojim nastankom povod za pritožbo Novomeščanov pri deželnem knezu, saj so se ustrašili, da bodo stavbni les za potrebe mesta v prihodnje morali dobavljati iz odročnejših predelov. Zato so zahtevali, naj se sporna naselja odstranijo. Prva dejanska omemba Podstenic sicer sega v leto 1614, ko je v vasi živel posestnik s priimkom Grill. Ime se je v lokalnem okolju ohranilo vse do 20. stoletja.
Podstenice so bile med roškimi vasmi v marsičem posebne. Od leta 1880 so bile edina vas v Rogu, v kateri so bili ob Kočevarjih vedno evidentirani tudi slovenski prebivalci. Poleg tega so bile eno redkih roških naselij, kjer je na prelomu iz 19. v 20. stoletje število vaščanov naraslo, medtem ko so drugod popisi večinoma zaznavali znaten upad. Čeprav so bile po letu 1910 tudi Podstenice izpostavljene podobnim trendom (leta 1921 je upad prebivalstva denimo znašal kar 36 %), pa se je v desetletju pred drugo svetovno vojno položaj začel znova izboljševati. Leta 1936 so popisovalci v vasi našteli 82 vaščanov, samo tri manj kot leta 1869, ko je v Podstenicah v devetih hišah živelo 85 ljudi.
Za naselje je bila pomembna lega ob glavni prometnici skozi Kočevski rog. Na prehodu iz 19. v 20. stoletje so Podstenice obiskovalcem v Dolenjskih Toplicah prav zato priporočali kot izhodišče za obisk vasi Kunč s tamkajšnjo ledeno jamo in ostanki stavbe, v kateri naj bi se nekoč skrivala Veronika Deseniška. Pred zadnjo svetovno vojno je mimo Podstenic vodila tudi markirana popotniška pot iz Podturna na Rog.
Poljedelstvo in živinoreja v Podstenicah nista bila dovolj izdatna, da bi zadostila vsem potrebam, zato so ljudje med obema vojnama zaslužek iskali v oglarjenju in prevažanju lesa, sprva na roško žago, po njenem zaprtju pa v Stražo. Gostilna družine Grill na tedanji hišni številki 7 je bila obenem shajališče furmanov, ki so iz roških gozdov vozili hlodovino. Leta 1938 je v Podstenicah začela obratovati še parna žaga lesnega trgovca Pogačnika iz Škofje Loke. V virih pa se v tridesetih letih ne omenja več proizvodnje domačih izdelkov iz bukovine, ki se je v vasi ohranjala še po letu 1900. Dobrega pol stoletja pred tem je ugasnila tudi peč za čiščenje in kalciniranje pepelike, ki je iz Podstenic nekoč pokrivala celotno območje Roga.
Decembra 1941 se je naselje, ki je od leta 1898 imelo celo lastno šolo, zapustilo 52 kočevarskih prebivalcev. Po spopadu s partizani, ki so v tako izpraznjenem prostoru formirali več ustanov, v podsteniški vili kneza Auersperga pa vzpostavili ambulanto, je italijanska vojska julija 1942 vas požgala. Kasneje je bila še dvakrat bombardirana. Ob koncu vojne je bilo zato vseh šestnajst hiš neuporabnih. Oblasti naselja, blizu katerega se nahajata dve brezni z žrtvami povojnih pobojev, niso več obnovile. V kraju, kjer so že Auerspergi imeli gozdno upravo, so tako uredile le logarsko in gozdarsko hišo, lovsko kočo ter bivališče za gozdne delavce s pripadajočim hlevom. Odstranjeni so bili tudi ostanki cerkve sv. Urha, ki je verjetno segala še v 18. stoletje. Po letu 2000 so lokalni čebelarji gozdarsko hišo preuredili v čebelarski dom z manjšo muzejsko zbirko. Stavbo so gradili nemški vojni ujetniki, z uporabo gradbenega materiala opustošenih hiš.
Z letom 2022 je državni statistični urad območje Podstenic z manj kot 0,08 prebivalca/km2 razglasil za formalno najredkeje poseljen kraj v državi. Prej je ta naziv pripadal roškemu naselju Trnovec, a se je zdaj uradno pridružilo 53 drugim slovenskim krajem brez stalno prijavljenih prebivalcev.
