As of 2001[update] India census, Nasrullaganj had a population of 17500. Males constitute 54% of the population and females 46%. Nasrullaganj has an average literacy rate of 66%, higher than the national average of 29.5%: male literacy is 74%, and female literacy is 57%. In Nasrullaganj, 15% of the population is under 6 years of age.
Around 25 km. from Nasrullaganj is the famous Salkanpur Temple of Goddess Durga. This sacred siddhpeeth of Vindhyavasni Beejasan devi (one of the incarnation of the Hindu goddess Durga) is on an 800 foot high hillrock, in the village Salkanpur near Rehti city, 70 km from Bhopal. The deity, Ma Durga Beejasan is held in high esteem by her followers & local. Thousands of people visit this place everyday climbing more than 1000 steps. Every year a grand fair is held in salkanpur during Navratris. It is very old Temple but at present temple renovate by Salkanpur Trust.