Podstenice was a later settlement compared to the oldest villages in the area, probably founded under the Counts of Blagay. It was not included in the 1574 land registry, but was mentioned for the first time in written sources in 1614. In 1770 the village had nine houses. A school was established in the village in 1888. In 1936 the village had 17 houses and a population of 82.
Mass graves
Podstenice is the site of three known mass graves associated with the Second World War. The Rog Road Mass Grave, also known as the Pocket Cave Mass Grave, is located on the left side of the road from Podturn pri Dolenjskih Toplicah to Kočevje. It contains the remains of civilian and military prisoners transported from prisons in Novo Mesto. The Rugar Slopes Cave Mass Grave is located on rocky terrain in a woods on the northern slope of a heavily karstified hill in a valley east of Mount Rog, south of Rog Road, in forest section 65 of the Poljane forest unit. It contains the remains of political opponents of the Yugoslav Partisan movement, Home Guard members and other soldiers subordinate to German forces that were murdered after the war, and possibly civilian victims as well. The Double Shaft by Cink Cross Mass Grave is located at the crossroads to Cinkon the road from Podstenice. The opening is long, starting below an old beech grove and continuing along a fence. It contains the remains of members of the Home Guard and other armed groups subordinate to the German forces that were murdered after the Second World War. The bottoms of both shafts are covered by large rocks that fell there from the surface and the entryways to the shafts were dynamited. The grave site is registered as cultural heritage.
Church
The local church was dedicated to Saint Ulrich and was an 18th-century building. It stood on the eastern edge of the village. It was a traditional stone structure with a rectangular barrel-vaulted nave and a narrower semicircular chancel. A three-story bell tower stood in front of the main entrance and had a simple pyramid roof with wooden shingles. The corners of the nave were fortified with quoining. The nave had two rectangular windows on each side; they were slightly rounded on the top, which was fashionable at the time and also allowed more light into the building. A new altar was installed in the church in the 1860s. New bells were purchased by Princess Auersperg from the Samassa foundry in Ljubljana and installed just before the outbreak of the First World War, but they were soon removed for military needs. After the war, emigrants in the United States collected money for new bells, which were installed in 1927. The church was renovated in 1932 and re-roofed with new shingles. The church was reduced to ruins in the Second World War, and in the mid-1950s the walls were pulled down and crushed into gravel for the local roads.
