We show that the wages of men and women are differentially affected by outside options, and that these differential responses contribute to the gender pay gap. We develop a simple model of on-the-job search that integrates two crucial gender differences: job preferences and the propensity to renegotiate wages in response to external offers. Both factors contribute to lower wage responsiveness for women when they receive outside offers, and a negative female-male pay gap. However, women’s job mobility responses vary depending on the underlying mechanism. To empirically test our model’s predictions, we analyze wage and job mobility responses of men and women to external job opportunities, mediated through family networks. Using Swedish register data, we find that improved outside options are associated with higher within-job wage growth for men but not for women. Importantly, we can rule out that these gendered responses arise from differences in the quality of external offers as these are balanced across genders by design. Additionally, men’s and women’s job mobility responses are very similar. In the light of the model, we attribute these findings to differences in negotiation behavior between men and women. Policies encouraging women to bargain in response to outside options may thus be a powerful tool for reducing the remaining within-job gender gap in pay.