The authorities have been offering incentives - providing cash to cover 80 per cent of scholastic costs - to see their reforms through.
This is proving to be hugely successful, bringing most madrassas under state supervision; religious schools that are largely funded by the government now follow both the state and religious curricula.
Zainul Abedine, the headmaster of the country's largest Islamic school, says: "In order to access government funds, many madrassas have opened their syllabus to other subjects like teaching languages such as English or Bengali. The number of madrassas have multiplied and so have the [numbers of] students".
With more then six million students currently enrolled, the madrassa system in Bangladesh is the second-largest in the world and is likely to get even larger as religious institutions open their doors to female students for the first time.
Maulana Abul Kalam Azad, a senior Islamic scholar, has welcomed the move to educate girls in madrassas.
"Girls are thriving – they tend to perform better than male students," he said.
A recent study by Nazmul Chaudhury, of the World Bank, found that young people's attitudes were interlinked with that of their teachers and that the presence of female instructors leads to increased openness in both female and male students.
In stark contrast to the allegations that madrassas cultivate intolerance, this study found that in Bangladesh "modernised religious education is associated with attitudes that are conducive to democracy".
The World Bank study goes further in asserting that the country's madrassas have helped Bangladesh accomplish some of the UN's Millennium Development Goals, particularly in achieving parity between boys and girls in schools.
"Fifty per cent of the students are female and particularly in rural areas, madrassas play an important role in [providing] girls with access to education," says Robert Floyd, the World Bank's country director in Bangladesh.
The acceptance of girls into a religious education system traditionally reserved only for boys has had a positive impact, leading to a wider understanding of the importance of female education.
Parents who may not have enrolled their daughters in secular schools are encouraged by the example set by equality in madrassas.
While many of the girls do not actively seek employment once they graduate, an increasing number go on to pursue higher education or take up careers in Islamic banking, a sector in which services are catering exclusively to women.
Nurul Islam Nahid, the education minister, believes the public perception of female education has started to change.
"In Muslim societies, when we were students of primary schools, girls going to school was very rare. Now it is a big achievement; the main challenge is that we want to bring all children to school," he said.
According to UN figures, some 48 per cent of the population is illiterate, and this - rather than militancy - is the main challenge that the country faces.
For the time being, the country's 20,000 madrassas appear to be the best equipped to fight this battle.