We examine how immigrants enter the labor market and whether their integration process varies by host country's immigration history. We focus on two countries - Finland and Sweden - that have similar formal institutions, but differ vastly in their past immigration experience. Nevertheless, in both countries, immigrants tend to find their first jobs in low-paying establishments where the manager and colleagues often share their ethnic background. Time to entry and entry job characteristics vary widely by region of origin. Furthermore, entry job characteristics predict earnings dynamics and job stability. The patterns and associations are remarkably similar in Finland and Sweden. These findings suggest strong regularities in labor market integration and ethnic segregation that are independent of immigration history and ethnic diversity.