Rationale: The population-level impact of malaria vaccines introduced through routine health systems depends on whether reductions in malaria burden occur consistently across implementation settings. However, facility-level variation in malaria trends following vaccine introduction remains poorly characterised. Evaluating heterogeneous responses after R21/Matrix-M roll-out is necessary to determine whether observed changes reflect a uniform programme effect or are driven by local epidemiological and health system factors. Objectives: To characterise the pattern, consistency, and correlates of change in facility-recorded malaria prevalence among children aged 5-11 months following R21/Matrix-M malaria vaccine roll-out in Ogbia Local Government Area, Bayelsa State, Nigeria. Methods: A retrospective facility-based observational analysis was conducted using routinely collected malaria and immunization records from nine primary healthcare facilities across four clans in Ogbia LGA. Facility-level malaria prevalence before and after vaccine roll-out was compared using prevalence ratios (PRs) with 95% confidence intervals. Heterogeneity was assessed using Cochran’s Q and I² statistics. Additional analyses examined clan-level differences, association between catchment population size and prevalence change, regression-to-the-mean effects, vaccine coverage associations, and facility-specific excess malaria episodes. Results: Across the nine facilities, malaria prevalence increased from 3.12% before roll-out to 6.30% after roll-out, corresponding to a pooled prevalence ratio of 2.02 (95% CI: 1.66-2.45; χ²=53.18; p<0.001). Facility-level changes were heterogeneous, with PRs ranging from 0.40 (95% CI: 0.08-2.04) to 12.00 (95% CI: 1.57-91.75). Significant between-facility heterogeneity was observed (Cochran’s Q=27.97, df=8, p<0.001; I²=71.4%; τ²=0.254). At clan level, prevalence increases differed significantly (Q=19.18, df=3, p<0.001; I²=84.4%), with Abureni showing the largest increase (PR=2.90; 95% CI: 2.03-4.14). Catchment population size was not significantly associated with prevalence change (Spearman ρ=0.650; p=0.058). Baseline prevalence did not predict subsequent change (Spearman ρ=0.117; p=0.765). Neither first-dose vaccine coverage (ρ=0.200; p=0.606) nor third-dose coverage (ρ=-0.05; p=0.910) was associated with prevalence change. Ogbia Central PHC, Otuogidi PHC, and Anyama PHC contributed 80.7% of the total excess malaria episodes observed after roll-out. Conclusion: Malaria prevalence increased after R21/Matrix-M roll-out, but the magnitude of change was highly heterogeneous across facilities and clans. The absence of associations with vaccine dose coverage, catchment population size, and baseline prevalence suggests that the observed variation was unlikely to be explained by vaccination coverage patterns alone. Thus, routine malaria vaccine monitoring should incorporate facility-level surveillance to identify local drivers of divergent malaria trends and guide targeted programme responses. The findings demonstrate that malaria vaccine implementation outcomes can vary substantially within the same geographical area. Identifying facility-specific contributors to changing malaria burden is essential for translating vaccine introduction into measurable public health impact.