This article has 3 main objectives: (1) to assess the prevalence of child labor in Colombia, (2) to identify factors associated with child labor, and (3) to determine whether social protection programs have an association with the prevalence of child labor in the country. Using a cross-sectional study with data from the Colombian Demographic and Health Survey 2010, a working child was defined as a child who worked during the week prior to the survey in an activity other than household chores. Through descriptive statistics, bivariate analysis, and multivariate regressions, it was found that child labor was associated with gender (boys were more likely to work), older age, ethnicity (children from indigenous communities were more likely to be workers), school dropout, disability (children with disabilities were less likely to be working), subsidized health social security system membership, and lower number of years of mother’s schooling. Furthermore, the results of this study suggest that children beneficiaries of the subsidy Familias en Acción were less likely to be working and that social protection programs were more effective to reduce child labor when targeting the lowest wealth quintiles of the Colombian population.