It has long been recognized that quasi-periodic oscillations (QPOs) in the X-ray light curves of accreting black hole. and neutron star binaries have the potential to be powerful diagnostics of strong field gravity. However, this potential cannot be fulfilled without a working theoretical model, which has remained elusive. Perhaps, the most promising model associates the QPO with Lense-Thirring precession of the inner accretion flow, with the changes in viewing angle and Doppler boosting modulating the flux over the course of a precession cycle. Here, we consider the polarization signature of a precessing inner accretion flow. We use simple assumptions about the Comptonization process generating the emitted spectrum and take all relativistic effects into account, parallel transporting polarization vectors toward the observer along null geodesics in the Kerr metric. We find that both the degree of linear polarization and the polarization angle should be modulated on the QPO frequency. We calculate the predicted absolute rms variability amplitude of the polarization degree and angle for a specific model geometry. We find that it should be possible to detect these modulations for a reasonable fraction of parameter space with a future X-ray polarimeter such as NASA's Polarization Spectroscopic Telescope Array (the satellite incarnation of the balloon experiment X-Calibur).