The aim of the present study was to explore the potential for using vermicompost from olive-mill waste as an organic amendment for enhanced bioremediation of polycyclic aromatic hydrocarbons (PAHs)-contaminated soils. The focus was to analyse the genetic potential and the naphthalene dioxygenase (NDO) expression of the bacterial communities involved in the degradation of naphthalene, as chemical model for the degradation of PAH. The structure of the metabolically active bacterial population was evidenced in the RNA-based denaturing gradient gel electrophoresis (DGGE) profiles. The relative expression of NDO was determined with real-time PCR in both the soil and the vermicompost cDNA. Naphthalene changed the structure of the metabolically active bacterial community in the vermicompost when this was artificially contaminated. When used as amendment, naphthalene-free vermicompost modified the bacterial population in the PAH-contaminated soil, evidenced in the DGGE gels after 1 month of incubation. In the amended soil, the vermicompost enhanced the NDO enzyme expression with a concomitant biodegradation of naphthalene. The effect of the vermicompost was to induce the expression of biodegradation indicator genes in the autochthonous bacterial community and/or incorporate new bacterial species capable of degrading PAH. The results indicated that vermicompost from olive-mill wastes could be considered a suitable technology to be used in PAH bioremediation.