This paper examines the labor market trajectories of refugees who arrived in Belgium between 2003 and 2009. Belgium has offered relatively easy formal labor market access to refugees but they face many other barriers in its strongly regulated and institutionalized labor market. Using the Belgian Labour Force Survey linked to longitudinal administrative data, we estimate event history models to compare refugees' entry into and exit out of the first employment, contrasting their outcomes with family and labor migrants of the same arrival cohort. The analysis shows that refugees take significantly longer to enter their first employment as compared to other migrant groups. They also run a greater risk of exiting out of their first employment into unemployment and (back) into social assistance. The results suggest that quick formal access clearly does not suffice for sustainable integration in the labor market. Additional education and labor market measures appear needed to enhance a more durable integration.