We demonstrate that temperature-programmed vibrational sum-frequency generation (SFG) spectroscopy has a unique sensitivity to certain adsorbate overlayer structural transitions. In the CO stretching vibration of co-adsorbed CO/O(2×1)/Ru(0001) we observe pronounced dips in the spectral intensity as the adsorbate overlayer undergoes structural transitions with temperature. Combining with temperature-programmed desorption (TPD) a more complete picture of temperature-dependent structural transitions is obtained. We extract kinetic parameters from the SFG data and obtain good agreement with TPD when both techniques see the same transition. Infrared-infrared visible SFG is used to determine changes in inter-adsorbate coupling that allow us to experimentally assign the structural transitions. Furthermore, density functional theory calculations of the proposed structures and energetics are performed to verify the experimental assignments.