Can “full and productive employment for all” be achieved by 2030 as envisaged by the United Nations Sustainable Development Goals? This paper assesses the issue for the largest 62 Colombian cities using social security administrative records between 2008 and 2015, which show that the larger the city, the higher its formal occupation rate. This is explained by the fact that formal employment creation is restricted by the availability of the diverse skills needed in complex sectors. Since skill accumulation is a gradual path-dependent process, future formal employment by city can be forecasted using either ordinary least square regression results or machine learning algorithms. The results show that the share of working population in formal employment will increase between 13 and nearly 32 percent points between 2015 and 2030, which is substantial but still insufficient to achieve the goal. Results are broadly consistent across methods for the larger cities, but not the smaller ones. For these, the machine learning method provides nuanced forecasts which may help further explorations into the relation between complexity and formal employment at the city level.