This paper constructs a theory of the coexistence of fixed-term and permanent employment contracts in an environment with ex-ante identical workers and employers. Workers under fixed-term contracts can be dismissed at no cost while permanent employees enjoy labor protection. In a labor market characterized by search and matching frictions, firms find optimal to discriminate by offering some workers a fixed-term contract while offering other workers a permanent contract. Match-specific quality between a worker and a firm determines the type of contract offered. We analytically characterize the firm's hiring and firing rules. Using matched employer-employee data from Canada, we estimate the wage equations from the model. The effects of firing costs on wage inequality vary dramatically depending on whether search externalities are taken or not into account.