This work aims to evaluate and compare, for the first time, the effects of extra virgin olive oil (EVOO) and hybrid palm oil (HPO) supplementation on the fatty acid profile and phospholipid (PL) molecular species composition of human erythrocyte membranes. Results supported the effectiveness of both HPO and EVOO supplementation (3 months, 25 mL/day) in decreasing the lipophilic index of erythrocytes with no significant differences between HPO and EVOO groups at month 3. On the other hand, the novel and rapid ultraperformance liquid chromatography–tandem mass spectrometry method used for PL analysis reveals an increase in the levels of phosphatidylcholine and phosphatidylethanolamine species esterified with polyunsaturated fatty acids. This work demonstrates the ability of both EVOO and HPO to increase the degree of unsaturation of erythrocyte membrane lipids with an improvement in membrane fluidity that could be associated with a lower risk of developing cardiovascular diseases.