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, it can be explained 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, if workers have low bargaining power, a higher minimum wage also increases firm profits and consequently employment. Therefore, the present article presents a new perspective on reasons for why minimum wages often have no or only negligible employment effects.