In many countries, Employment Protection Legislation (EPL) establishes different regulations for certain groups of workers who face more disadvantages in the labor market (young workers, women, unskilled workers, etc.) with the aim of improving their employability. Well-known examples are the introduction of atypical employment contracts (e.g. temporary and determined-duration contracts) which ease firing restrictions for some, but not all, workers. This paper discusses the effects of EPL varying among workers of different skills on the level and composition of unemployment, job flows, productivity and welfare. By using an extension of Mortensen-Pissarides’ (1994) search model where heterogeneous workers compete for the same jobs, we are able to identify several key channels through which changing firing costs for some groups of workers affects hiring and firing of all workers and, hence, may have a different impact on aggregate labor market variables than reducing firing costs across the board. Some analytical and simulation results also show that these effects of differentiated firing costs by workers’ skills may be different depending upon the initial state of the labor market.