A new hybrid nanomaterial is used in a screen-printed electrode (SPE) for sensing of the ortho-diphenols oleuropein (OLEU) and hydroxytyrosol (HYT) in extra virgin olive oil (EVOO) and related samples. The hybrid material consists of carbon black (CB) and molybdenum disulfide (MoS2). In comparison with individual nanomaterials, CB-MoS2 exhibits improved charge-transfer ability, low charge-transfer resistance, high electrical conductivity and enhanced electrocatalysis. The sensor is also characterized by (a) high sensitivity that avoids the need for adsorptive voltammetry, (b) reduced analysis time, and (c) high anti-fouling ability (electrode RSDOLEU < 8%, for n = 10). OLEU can be detected in the 0.3 to 30 μM concentration range with a 0.1 μM LOD, and HYT in the 2–100 μM range with a 1 μM LOD. A comparison of the data obtained by this sensor and by HPLC-UV exhibited high correlation (r = 0.995, p < 0.05). These data revealed the reliability of CB-MoS2 for analysis of complex EVOO and related samples.