The adoption of planted fallow largely depends on the cost and feasibility of using the technology; easy, inexpensive and simple fallow establishment methods are known to greatly enhance adoption. It was the objective of this study to assess the effects of weeding regime on the establishment of Calliandra calothyrsus and Inga edulis on degraded acid soils in southern Cameroon. A combination of the two fallow species and two weeding regimes, weeding or not weeding, were compared to a natural fallow. The trial was conducted in two sites of different base saturation levels with four replications. The results indicate that differences between the two species and the two weeding regimes were statistically significant (p < 005) on both sites for all measured tree growth parameters, as well as the residual effects on subsequent maize grain yield. Presence of weeds reduced stem diameter and height of C. calothyrsus and I. edulis at the early stage of their establishment. Weeding doubled the leaf biomass of both species. The highest woodmass was produced by Inga in plots with weeding treatment, with 48 t/ha of dry material. Tree fallow improved the yield of succeeding crops by twofold over the natural grass fallow. Weeding treatment improved maize yield, from 1.9t/ha to 2.8 t/ha after Calliandra fallow, and from 2.22 t/ha to 3.0 t/ha after Inga fallow. The significant effects of weeding treatments implies that fallow-improving tree species should be planted in relay intercropping for trees to benefit from the weeding of crops, thus reducing the labour spent on fallow establishment.