We compute the leading probability for a gluon to flip helicity state upon traversing a background plane wave gauge field in pure Yang-Mills theory and QCD, with an arbitrary number of colours and flavours. This is a one-loop calculation in perturbative gauge theory around the gluonic plane wave background, which is treated without approximation (i.e., to all orders in the coupling). We introduce a background-dressed version of the spinor helicity formalism and use it to obtain simple formulae for the flip amplitude with pure external gluon polarizations. We also give in-depth examples for gauge group SU(2), and evaluate both the high- and low-energy limits. Throughout, we compare and contrast with the calculation of photon helicity flip in strong-field QED.