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 (or are offered) worse wage bargains with their employers than men. Using longitudinal data on the hourly wages of Portuguese workers matched with income statement information for firms, we show that the wages of both men and women contain firm-specific premiums that are strongly correlated with simple measures of the potential bargaining surplus at each firm. We then show how the impact of these firm-specific pay differentials on the gender wage gap can be decomposed into a combination of sorting and bargaining ...