Most massive stars end their lives as red supergiants (RSGs), a short-lived evolutionary phase when they are known to pulsate with varying amplitudes. The RSG period-luminosity (PL) relation has been measured in the Milky Way, the Magellanic Clouds and M33 for about 120 stars in total. Using over 1500 epochs of R-band monitoring from the Palomar Transient Factory survey over a five-year period, we study the variability of 255 spectroscopically cataloged RSGs in M31. We find that all RGSs brighter than MK −10 mag (log(L/L ) > 4.8) are variable at ΔmR > 0.05 mag. Our period analysis finds 63 with significant pulsation periods. Using the periods found and the known values of MK for these stars, we derive the RSG PL relation in M31 and show that it is consistent with those derived earlier in other galaxies of different metallicities. We also detect, for the first time, a sequence of likely first-overtone pulsations. Comparison to stellar evolution models from MESA confirms the first-overtone hypothesis and indicates that the variable stars in this sample have 12 M < M < 24 M . As these RSGs are the immediate progenitors to Type II-P core-collapse supernovae (SNe), we also explore the implication of their variability in the initial-mass estimates for SN progenitors based on archival images of the progenitors. We find that this effect is small compared to the present measurement errors.