We develop new tests for the completeness of rural labor markets. The tests are based on a theoretical link between a shortage or surplus in the labor market and asymmetric responses to changes in household composition over time. We develop auxiliary tests to distinguish other types of market failures from labor market failures, and provide evidence that most changes in household composition are exogenous to local labor market conditions. We implement our test using nationally representative panel data from Ethiopia, Malawi, Tanzania, and Uganda. The overall pattern is one of excess supply of labor in rural areas, but there is substantial heterogeneity across cultivation phases, genders, and agro-ecological zones. Excess supply of labor is most evident during low-intensity cultivation phases (e.g., weeding). In Ethiopia, findings suggest that poor households face a de facto labor shortage, driven more by financial market failures than a physical shortage of available workers. There is evidence of partial gender segmentation in labor markets. In all four countries, women are more difficult to replace than men.