Using linked employer-employee data from Brazil, we document a large gender pay gap due to women working at lower-paying employers with better amenities. To interpret these facts, we develop an equilibrium search model with endogenous firm pay, amenities, and employment. We provide a constructive proof of identification of all model parameters. The estimated model suggests that amenities are important for 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.