Extra virgin olive oil (EVOO) is recognized for its nutritional virtues and the beneficial health effects deriving from its hydrophilic fraction (phenolic acids, phenolic alcohols, flavonoids, and secoiridoids). The phenolic compounds of EVOOs possess multiple biological properties such as antioxidant, antimicrobial, anticarcinogenic, and anti-inflammatory properties, among others. Considering that EVOOs produced in Greece are recognized as high-quality products due to their rich phenolic content, it is imperative to characterize Greek monovarietal EVOOs and ensure that their uniqueness is closely linked to their botanical and territorial origin. In this work, an ultra-high-performance liquid chromatography–quadrupole time-of-flight tandem mass spectrometry (UHPLC-QTOF-MS) analytical method combined with target and suspect screening was used to characterize monovarietal EVOOs of the Kolovi variety from Lesvos, and thereby establish their phenolic fingerprint. Overall, 25 phenols were determined, and the total quantification and semi-quantification results ranged between 251 and 1230 mg/kg, highlighting the high phenolic content of the Kolovi variety from the island of Lesvos in the North Aegean.