The Escherichia coli AlkB protein is a 2-oxoglutarate/Fe(II)-dependent demethylase that repairs alkylated single stranded and double stranded DNA. Immunoaffinity chromatography coupled with mass spectrometry identified RecA, a key factor in homologous recombination, as an AlkB-associated protein. The interaction between AlkB and RecA was validated by yeast two-hybrid assay; size-exclusion chromatography and standard pull down experiment and was shown to be direct and mediated by the N-terminal domain of RecA. RecA binding results AlkB-RecA heterodimer formation and RecA-AlkB repairs alkylated DNA with higher efficiency than AlkB alone. © 2016 The Author(s) 2016. Published by Oxford University Press on behalf of Nucleic Acids Research.