Estimating the density of large, feral species such as wild horses at landscape scales can present a logistical hurdle for wildlife managers attempting to set density-based management targets. We undertook aerial surveys of wild horses by using a helicopter in Guy Fawkes River National Park in north-eastern New South Wales across 3 years to determine whether meaningful density estimates could be obtained efficiently by a mark–recapture technique based on recognition of individual horses. Horse groups photographed from the air on the first of two surveys conducted each year were ‘marked’ on the basis of a unique combination of colours and natural markings, and ‘recaptured’ if they were photographed and identified on the second survey. Population size was estimated with the program MARK using a range of population estimators; however, because horses appeared to be evading detection on the second survey of each year, we chose a final estimation model that accounted for detection shyness in the study species. In 2005, the density estimate was 3.8 horses per km² (upper and lower 95% CL = 3.5–5.7 horses per km²). Following horse control in these catchments, the estimate in 2007 was 2.3 horses per km² (upper and lower 95% CL = 2.1–3.4 horses per km²), and this change in density can be accounted for by the known number of horses removed from the survey area between survey periods. Overall, the technique proved useful for estimating densities of wild horses in deeply dissected gorge country where other estimation techniques (such as line transects) are not practical; however, low recapture rates in one of the years of the study shows that the technique may not always be applicable. Our technique should also be suitable for surveying other large mammals with broad ranges in open environments, provided recognition of individuals from unique marks is possible.