In this study, we investigate how the attitude of natives—defined as the perceived trustworthiness of citizens from different countries—affects immigrants’ labor market outcomes in Germany. Evidence in the literature suggests that barriers to economic assimilation might be higher for some groups of immigrants, but the role of natives’ heterogeneous attitudes toward immigrants from different countries of origin has received little attention. Using individual-level panel data from the German Socio-Economic Panel covering the years 1984 to 2014, we apply survival analysis methods to model immigrants’ unemployment durations. We find that lower levels of trust expressed by natives toward the citizens of a given country, measured using Eurobarometer surveys, are associated with increased unemployment durations for immigrants from this country. We show that this result is not driven by origin-specific unobserved heterogeneity and that it is robust to different specifications and alternative explanations.