Bacteria have enormous catabolic potential for remediating wastes; however, the interactions between bacteria and pollutants are complex and suitable remediation does not always take place. Hence, molecular approaches are being applied to enhance bioremediation. Here, an overview is provided of the recent advances in bioremediation by utilizing rhizoremediation, protein engineering, metabolic engineering, whole-transcriptome profiling, and proteomics for the degradation of recalcitrant pollutants such as chlorinated aliphatics and polychlorinated biphenyls as well as for binding heavy metals.