The 1,080 km2 Batang Gadis National Park in the North Sumatra province of Indonesia was established in December 2004 by the regional government of Mandailing Natal district. The Park has the potential to make an important contribution to tiger conservation but lacks scientific data on the occurrence of the species. This study aimed to assess the tiger population of the Park, using camera trapping conducted between December 2005 and July 2006. We recorded a mean tiger density of 1.8 tigers per 100 km2 (95% CI 1.8–6.4) and, based on this, estimated the tiger population in and adjacent to the Park to be 29–103 adults. We found that tiger presence was negatively correlated with altitude and positively correlated with distance from forest edge to the interior, and < 18% of the total suitable habitat occupied by tigers was of high quality. This study indicates that Batang Gadis National Park potentially serves as a natural corridor betwen the Angkola and Barumun-Rokan ecosystems, areas totalling c. 6,500 km2, and that this landscape could serve as a stronghold for tiger populations in northern Sumatra.