Marine harbor sediments are frequently polluted with significant amount of polycyclic aromatic hydrocarbons (PAHs) some of which are naturally toxic, recalcitrant, mutagenic, and carcinogenic. To stimulate biodegradation of PAHs in PAH-contaminated sediments collected from near Gwangyang Bay, Korea, lactate was chosen as a supplementary carbonaceous substrate. Sediment packed into 600 ml air-tight jar was either under no treatment condition or lactate amended condition (1%, w/v). Microbial community composition was monitored by bacteria-specific and archaea-specific PCR-terminal restriction fragment length polymorphism (T-RFLP), in addition to measuring the residual PAH concentration. Results showed that lactate amendment enhanced biodegradation rate of PAHs in the sediment by 4 to 8 times, and caused a significant shift in archaebacterial community in terms of structure and diversity with time. Phylogenetic analysis of 23 archaeal clones with distinctive RFLP patterns among 288 archaeal clones indicated that majority of the archaeal members were closest to unculturable environmental rDNA clones from hydrocarbon-contaminated and/or methanogenesis-bearing sediments. Lactate amendment led to the enrichment of some clones that were most closely related to PAH-degrading Methanosarcina species. These results suggest a possible contribution of methanogenic community to PAH degradation and give us more insights on how to effectively remediate PAH-contaminated sediments.