Labor informality, associated with low productivity and lack of access to social security services, dogs developing countries around the world. Rates of labor (in)formality, however, vary widely within countries. This paper presents a new stylized fact, namely the systematic positive relationship between the rate of labor formality and the working age population in cities. We hypothesize that this phenomenon occurs through the emergence of complex economic activities: as cities become larger, labor is allocated into increasingly complex industries as firms combine complementary capabilities derived from a more diverse pool of workers. Using data from Colombia, we use a network-based model to show that the technological proximity (derived from worker transitions between industry pairs) of current industries in a city to potential new complex industries governs the growth of the formal sector in the city. The mechanism proposed has robust strong predictive power, and fares better than alternative explanations of (in)formality.