Pearl millet (Pennisetum glaucum (L.) R. Br.) is an important staple cereal cultivated in the arid and semi-arid tropics of Asia and Africa, regions severely affected by malnutrition. Knowledge about the extent of genetic variability and patterns of agro-morphological variation in local germplasm from a target region is an important prerequisite for efficient crop improvement. To assess the potential of Sudanese pearl millet landraces as sources of desirable traits for pearl millet improvement including biofortification, a total of 225 accessions were evaluated in Sudan at three locations for agro-morphological traits and at one location for grain mineral nutrient contents (Fe, Zn, Ca, P, K, Mg, Mn, S, Na, Cu and β-carotene). Genetic variation was highly significant, but relatively limited for some agro-morphological traits (62–78 d to flowering, 119–188 cm plant height and 16–34 cm panicle length), pointing to the potential usefulness of a targeted diversification for these traits. Self-pollinated grain micronutrient contents showed a wide variation: 19.7–86.4 mg/kg for Fe and 13.5–82.4 mg/kg for Zn. Significant and positive correlations among most of the nutritional traits were observed; therefore, enhancement of the concentrations of some nutrients will lead to the improvement of other related nutrients. No significant associations were observed between the nutritional and agro-morphological traits, indicating good prospects for simultaneous improvement of both trait categories. No clear patterns of geographic differentiation for specific traits were detected for the Sudanese pearl millet. Nutrient-rich accessions were identified and those with acceptable agro-morphological traits are encouraging materials for future pearl millet biofortification programmes in Sudan.