The stability of refined, bleached, and deodorized palm olein (RBDPO) was studied under controlled heating conditions. RBDPO was heated continuously for 24 h at 160, 170, and 180 °C, with oil sampled at four hour intervals. Thermo-oxidative alterations were measured through various parameters, such as monomeric oxidized triacylglycerols (oxTAG), total polar compounds (TPC), polymerized triacylglycerols (PTG), oxidative stability, and fatty acid composition. After 24 h of heating, the TPC and triacylglycerol oligomers showed a linear increase with heating time at all heating temperatures. At the end of the heating study, more epoxy acids were formed than keto and hydroxy acids. Moreover, caprylic acid, which was not present in fresh oil, was formed in significant amounts. The increase in oxTAG was strongly correlated with the increase in the p-anisidine value and total oxidation value. The decreases in diacylglycerol and free fatty acids were strongly correlated with an increase in PTG.