This paper analyzes the labor market integration of non-European refugees originating from middle- and low-income countries for the period of 2009–2018 in Austria. We assess their probability of being employed relative to Austrian natives and compare it with that of other non-European migrants and European refugees and other immigrants from low- and middle-income non-EU countries. We draw on a register-based panel dataset covering the complete labor market careers of all individuals residing in Austria. We control for macrolevel explanatory variables (e.g., the labor market situation at the time and the place of settlement) and individual characteristics. The analysis shows that initial refugee employment gaps relative to natives are large in the first years, when labor market access is difficult. After a period of 7 years, the unconditional gap between refugees and natives declines to 30 percentage points, similar to that of other migrants, but the gap is still decreasing. After controlling for a set of explanatory variables, the conditional gap amounts to only 10 percentage points at that time. Moreover, our analysis provides insights into differences in employment gaps across population subgroups of immigrant groups and natives by gender, age, education level, and types of employment.