Using linked employer-employee data from Brazil, we document a large gender pay gap due to women working at lower-paying employers with better nonpay attributes. To interpret these facts, we develop an equilibrium search model with endogenous firm pay, amenities, and hiring. We provide a constructive proof of identification of all model parameters. The estimated model suggests that amenities are important for both men and women, that compensating differentials explain half of the gender pay gap, and that there are significant output and welfare gains from eliminating gender differences. However, equal-treatment policies fail to achieve those gains.