The need to give incentives is usually absent in the literature on minimum wages. However, especially in the service sector it is important how well a job is done, and employees must be incentivized to perform accordingly. Furthermore, many aspects regarding service quality cannot be verified, which implies that relational contracts have to be used to provide incentives. The present article shows that in this case, a minimum wage increases implemented effort, i.e., realized service quality, as well as the efficiency of an employment relationship. Hence, this paper can explain why productivity and service quality went up after the introduction of the British National Minimum Wage, and that this might actually have caused a more efficient labor market. Furthermore, several empirically observed implications of a (higher) minimum wage can be explained. It might reduce turnover of employees, have spillover effects on higher wages, and reduce wage dispersion.