Despite the fact that several approaches have been applied for the bioremediation of olive mill wastewaters, little information is available on bacteria inhabiting these agro-industrial effluents. In the present study, 16S rRNA gene clone libraries were constructed to identify bacterial diversity in olive-oil mill wastewaters generated by two olive varieties, Olea europaea var. mastoidis and O. europaea var. koroneiki. Due to chloroplast excess in wastewater produced from the processing of O. europaea var. koroneiki, a clone library using specific PCR primers for β-Proteobacteria was further constructed. The bacterial diversity in O. europaea var. mastoidis-generated olive mill wastewaters consisted mainly of members of Acetobacteriaceae, Prevotellaceae and Lactobacillaceae, while the majority of β-proteobacteria identified in O. europaea var. koroneiki-generated olive mill wastewaters were placed within the families Comamonadaceae, Oxalobacteraceae, Hydrogenophilaceae and Rhodocyclaceae. At least 17 novel phylogenetic linkages among Bacteria were identified. Olive-oil mill wastewaters microbiota appears to have originated from soil and freshwater environments, while the cultivation and harvesting practice highly influenced the bacterial community structure in olive mill wastewaters. The presence of fecal bacteria in O. europaea var. mastoidis-generated olive mill wastewaters, due to the long harvesting period, should be of concern.