Visceral leishmaniasis (VL) is a life-threatening parasitic disease, transmitted by a sandfly. A survey was conducted to estimate the VL incidence in 45 villages located in the eastern part of Gedaref State, the main endemic focus of VL in Sudan. Between the 5th of May and the 17th of June 2011, we interviewed 17,702 households for a population of 94,369. Sixteen individuals were diagnosed with primary VL through active case-detection, and 725 reported VL treatment over the past year. The overall incidence rate of VL over the past year was 7.0/1000 persons per year. The crude mortality rate over the mean recall period of 409 days was 0.13/10'000 persons per day. VL was a possible or probable cause for 19% of all deaths. Taking also into account the VL-specific mortality of 0.9/1000 per year, the incidence was estimated at 7.9/1000 per year. Overall, 12.5% of the population reported having been treated for VL in the past. VL is a major public health issue in Gedaref. Active VL case detection had a very low yield in a context of adequate access to care. Such strategy seems redundant if patients already have access to care.