This work examines the formation of poly-microbial communities adhered to the epidermis of natural green Gordal olives and the application of different methodologies for recovery and counting of the microorganisms embedded in olive biofilms. The fermentation process was physicochemical and microbiologically monitored for 90 days, at which, formation of true biofilms on the skin of fermented fruits was confirmed by scanning electron microscopy. Then, samples of olives were taken and treated with sonication, enzymes, mechanical homogenization with stomacher and ultrasonic bath for biofilm disaggregation. The use of the stomacher for 1 min was the most effective treatment to release the lactic acid bacteria (6.6 log10 cfu g−1), whereas sonication for 5 min was the most efficient method for quantification of yeasts (up to 3.5 log10 cfu g−1). Molecular identification of isolates obtained from natural Gordal olive biofilms revealed that Lactobacillus pentosus was the only species found among lactic acid bacteria, while Pichia membranifaciens was the dominant yeast species, with higher counts obtained for the bacteria.