The subtype C Eastern Africa clade (CEA), a particularly successful HIV-1 subtype C lineage, has seeded several sub-epidemics in Eastern African countries and Southern Brazil during the 1960s and 1970s. Here, we characterized the past population dynamics of the major CEA sub-epidemics in Eastern Africa and Brazil by using Bayesian phylodynamic approaches based on coalescent and birth-death models. All phylodynamic models support similar epidemic dynamics and exponential growth rates until roughly the mid-1980s for all the CEA sub-epidemics. Divergent growth patterns, however, were supported afterwards. The Bayesian skygrid coalescent model (BSKG) and the birth-death skyline model (BDSKY) supported longer exponential growth phases than the Bayesian skyline coalescent model (BSKL). The BDSKY model uncovers patterns of a recent decline for the CEA sub-epidemics in Burundi/Rwanda and Tanzania (Re < 1) and a recent growth for Southern Brazil (Re > 1); whereas coalescent models infer an epidemic stabilization. To the contrary, the BSKG model captured a decline of Ethiopian CEA sub-epidemic between the mid-1990s and mid-2000s that was not uncovered by the BDSKY model. These results underscore that the joint use of different phylodynamic approaches may yield complementary insights into the past HIV population dynamics.