Essential mineral (iron and zinc) deficiencies are still prevalent in the Semi-arid Tropics, where many people consume monotonous, predominantly cereal-based diets. This study aimed to evaluate the potential of including tropical plant foodstuffs high in iron and zinc (moringa leaves and roselle calyces) or mineral availability enhancers (baobab fruit pulp) in a pearl millet-based food containing a plant food-based provitamin A source, with the aim of preventing iron and zinc deficiencies in the Semi-arid Tropics. Mineral bioaccessibility was assessed by dialysability assay. Moringa, roselle and baobab considerably increased iron and zinc bioaccessibility when added at 10 parts:100 parts pearl millet (dry basis). These foodstuffs, increased the contribution to the absolute iron requirements of women of reproductive age by 2.5, 2.1 and 2.3 times for moringa, roselle and baobab, respectively and to their absolute zinc requirements by 2.4, 2.1 and 2.7 times, respectively. Combining these plant foodstuffs could contribute up to 28% and 41% of the women’s absolute iron and zinc requirements, respectively, from a single meal. Moringa, despite having the highest iron content, when added at a very high level (30 parts:100 parts pearl millet) decreased bioaccessible iron and zinc, most probably primarily due to its high calcium content. Food-to-food fortification of staple cereal foods with moringa leaves, roselle calyces or baobab fruit pulp plus a provitamin A source can potentially sustainably improve iron and zinc bioavailability in the diets of at-risk communities in the Semi-arid Tropics.