Once again, agricultural mechanization is top on the policy, research, and development agendas in sub-Saharan Africa. However, whether labor is limiting in this region—and mechanization is in demand—remains debated. The hypothesis of this study is that labor is a major limiting factor to the productivity of most farming systems in Africa. We used farm-level data (including detailed labor data) from eight sites dominated by smallholder agriculture and spanning four countries in Eastern and Southern Africa, and analyzed this unique dataset using multivariate methods (generalized linear models, boundary line analysis, and binary classification and regression trees). Labor and/or other sources of farm power (draught power or tractor power) were found to limit land productivity in all study sites. We also found that the overall contribution of female labor to farming was much lower than commonly stated—between 7 and 35%—and that the labor intensity experienced by women in agriculture was dependent to a large degree on men’s tasks. Our results reveal a much higher demand for mechanization than previously found by macroeconomic analyses, and point to a problem of access rather than demand. Our results also add to recent evidence debunking the persistent myth that women provide the bulk of the farming labor, and demonstrate that reducing labor intensity experienced by women in farming depends to a large degree upon understanding labor intensity experienced by men, rather than poorly founded generalizations about how women are overworked. This is the first time farm-level data containing detailed labor assessment and spanning four countries are used to assess mechanization demand in Africa. This paper also plays a pioneering role in debunking a number of myths related to labor in African smallholder agriculture, with implications for the mechanization agenda of the region.