We study the gender pay gap in the labor market for CEOs by analysing 1,174 outsider CEO successions over the past three decades across 18 countries. We find that male and female CEOs receive a similar compensation overall but this masks marked gender differences in the pay structure: namely, women CEOs receive a lower proportion of fixed to total compensation than comparable men. We interpret this outcome as the result of gendered risk preferences, which exacerbate the pay gap when there is bargaining over pay, and contribute a theoretical model of the CEO labor market to formalise this intuition. The model also suggests that a more balanced gender composition in companies' boards can help women close the gap in pay structure—an hypothesis that is empirically supported in our data.