This paper examines the labor market integration of Venezuelan migrants in Colombia during a large-scale regularization program. Using labor force survey data on Venezuelan-born migrants and longitudinal data for the universe of regularized migrants, I find that migrants are much more likely than comparable natives to work informally, and only a small share of regularized migrants end up in formal jobs. Those who enter the formal sector earn substantially less than natives, and up to half of this wage gap is due to their sorting into lower-paying firms. Comparing job movers, I show that as migrants transition to better-paying firms, they do not capture their pay premiums fully. There are some improvements as regularized migrants gain formal sector experience, but most of the gap remains after five years. I discuss why formalization rates are not higher despite migrants' similar language, culture, education, and near-universal access to work permits.