The consumption of antioxidant-rich foods such as virgin olive oil (VOO) promotes high-density lipoprotein (HDL) anti-atherogenic capacities. Intake of functional VOOs (enriched with olive/thyme phenolic compounds (PCs)) also improves HDL functions, but the gene expression changes behind these benefits are not fully understood. Our aim was to determine whether these functional VOOs could enhance the expression of cholesterol efflux-related genes. In a randomized, double-blind, crossover, controlled trial, 22 hypercholesterolemic subjects ingested for three weeks 25 mL/day of: (1) a functional VOO enriched with olive oil PCs (500 mg/kg); (2) a functional VOO enriched with olive oil (250 mg/kg) and thyme PCs (250 mg/kg; FVOOT), and; (3) a natural VOO (olive oil PCs: 80 mg/kg, control intervention). We assessed whether these interventions improved the expression of cholesterol efflux-related genes in peripheral blood mononuclear cells by quantitative reverse-transcription polymerase chain reactions. The FVOOT intervention upregulated the expression of CYP27A1 (p = 0.041 and p = 0.053, versus baseline and the control intervention, respectively), CAV1 (p = 0.070, versus the control intervention), and LXRβ, RXRα, and PPARβ/δ (p = 0.005, p = 0.005, and p = 0.038, respectively, relative to the baseline). The consumption of a functional VOO enriched with olive oil and thyme PCs enhanced the expression of key cholesterol efflux regulators, such as CYP27A1 and nuclear receptor-related genes.