Savannas and adjacent vegetation types like gallery forests are highly valuable ecosystems contributing to several ecosystem services including carbon budgeting. Financial mechanisms such as REDD+ (Reduced Emissions from Deforestation and Forest Degradation) can provide an opportunity for developing countries to alleviate poverty through conservation of its forestry resources. However, for availing such opportunities carbon stock assessments are essential. Therefore, a research study for this purpose was conducted at two protected areas (Nazinga Game Ranch and Bontioli Nature Reserve) in Burkina Faso. Similarly, analysis of various vegetation parameters was also conducted to understand the overall vegetation structure of these two protected areas. For estimating above ground biomass, existing allometric equations for dry tropical woody vegetation types were used. Compositional structure was described by applying tree species and family importance indices. The results show that both sites collectively contain a mean carbon stock of 3.41 ± 4.98 Mg·C·ha−1. Among different savanna vegetation types, gallery forests recorded the highest mean carbon stock of 9.38 ± 6.90 Mg·C·ha−1. This study was an attempt at addressing the knowledge gap particularly on carbon stocks of protected savannas—it can serve as a baseline for carbon stocks for future initiatives such as REDD+ within these areas.