Of the three subspecies of Critically Endangered Bornean orangutans, Pongo pygmaeus pygmaeus has the smallest population size. One of its most important habitats is the tropical forest within and around Danau Sentarum National Park (DSNP). Research in the late 1990s estimated that ca. 1025 orangutans inhabited DSNP, while ca. 1717 orangutans inhabited the forest beyond DSNP's boundaries. However, concerns were later raised that incorrectly estimated nest decay rates (t values) may have led to the overestimation of the population size. Furthermore, the area experienced forest degradation and land use change between 2000 and 2013. Given these changing landscapes, updated population estimates were needed to inform policy makers and land-use planners on the implications of habitat loss for resident orangutans. We conducted this study to recalculate nest decay rates based on current recommended methods, and to update our knowledge on the orangutan population in the region. Our average nest decay rate was 288.3 days; applying this to the study in the late 1990s generated estimates of 807 individuals within DSNP and 1578 beyond DNSP's boundaries. New surveys of the transects undertaken between 2010 and 2014 revealed that the population size had declined substantially in these two areas, to 202 and 71 individuals respectively. Both declines are considerable, but larger losses occurred in logged-over and cleared forests outside the park. We discuss factors potentially driving these declines, emphasizing the need to improve habitat protection both inside and outside of DSNP, and make recommendations for improving the prospects for future orangutan conservation.