Olive fruits contain high concentrations of phenols that include phenolic acids, phenolic alcohols, flavonoids, and secoiridoids. The final concentration of phenols is strongly affected by brine conditions. The factors involved in modification by brine are still partially unknown and can include hydrolysis of secoiridoid glucosides and the release of hydrolyzed products. In this study olives from various Italian cultivars were processed by natural fermentation (e.g., without a preliminary treatment of olives with NaOH) using a selected Lactobacillus strain. Processed olives are characterized by a low phenolic concentration of phenols, consisting mainly of phenyl alcohols, verbascoside, and the dialdehydic form of decarboxymethylelenolic acid linked to (3,4-dihydroxyphenyl)ethanol (3,4-DHPEA-EDA), whereas a high level of phenols occurs in olive brine from all the cultivars studied. Olives of the Coratina cultivar, control and with fermentation by Lactobacillus pentosus 1MO, were analyzed in a frozen hydrated state by cryo scanning electron microscopy and energy-dispersive X-ray microanalysis, on both surface and transversal freeze-fracture planes. Structural modifications, found in olives after fermentation, may explain the phenol release in brine.