Background : A growing number of primarily qualitative studies have shown that the legal trajectories of immigrants in Western countries are often complex. However, immigrants' long-term legal trajectories remain a blind spot in quantitative migration research. Objective : This paper aims to provide new empirical insights into the variety of legal pathways among non-European immigrants who arrived in Belgium between 1999 and 2008. We build a typology of legal trajectories, and we investigate how these trajectories are related to immigrants' country of origin, asylum status, and social ties in Belgium. Methods : The micro longitudinal data is from the Belgian National Register. We use sequence analysis to identify clusters of legal trajectories, and multinomial logistic regressions to explore how they are related to immigrants' characteristics. Results : We identify seven types of legal trajectory. While some are simple and smooth, others are characterized by moves back and forth between legal statuses and frequent periods of irregularity. Immigrants from the least developed countries and rejected asylum seekers are more likely to experience slow and chaotic trajectories. By contrast, simple and short trajectories are more common among immigrants from higher- or middle-income countries. We also find that social and family ties are a key factor in long-term immigrants experiencing smooth legal trajectories. Conclusions : Legal statuses vary substantially over time, and trajectories differ widely among immigrants. Some categories of immigrants are more at risk of highly precarious long-term trajectories that may lead to situations of 'permanent temporariness'. Contribution : The paper highlights the relevance of a quantitative longitudinal perspective on immigrants' legal status and underlines the need to take into account not only the legal status upon arrival but also the complexity of legal trajectories during the stay in the destination country.