There is growing evidence that firm-specific pay premiums are an important source of wage inequality. These premiums will contribute to the gender wage gap if women are less likely to work at high-paying firms or if women negotiate worse wage bargains with their employers than men. Using longitudinal data on the hourly wages of Portuguese workers matched with balance sheet information for firms, we show that the wages of both men and women contain firm-specific premiums that are strongly correlated with employer productivity. We then show how the impact of these firm-specific pay differentials on the gender wage gap can be decomposed into a combination of bargaining and sorting effects. Consistent with the bargaining literature, we find that women receive only 90% of the firm-specific pay premiums earned by men. Notably, we obtain very similar estimates of the relative bargaining power ratio from our analysis of between-firm wage premiums and from analyzing changes in firm-specific premiums over time. We also find that women are less likely to work at firms that pay higher premiums to either gender, with sorting effects being most important for lower-skilled workers. Taken together, the bargaining and sorting effects explain about one-fifth of the cross-sectional gender wage gap in Portugal. Our results suggest that regulatory policies aimed at ensuring equal pay are likely to have their greatest benefit for high skilled women, whereas policies ensuring that women are fairly represented in the hiring pool of firms will have effects throughout the skill distribution.