The Fe(II)- and 2-oxoglutarate (2OG)-dependent dioxygenase AlkB from E. coli is a demethylase which repairs alkyl lesions in DNA, as well as RNA, through a direct reversal mechanism. Humans possess nine AlkB homologs (ALKBH1-8 and FTO). ALKBH2 and ALKBH3 display demethylase activities corresponding to that of AlkB, and both ALKBH8 and FTO are RNA modification enzymes. The biochemical functions of the rest of the homologs are still unknown. To increase our knowledge on the functions of ALKBH4 and ALKBH7 we have here performed yeast two-hybrid screens to identify interaction partners of the two proteins. While no high-confidence hits were detected in the case of ALKBH7, several proteins associated with chromatin and/or involved in transcription were found to interact with ALKBH4. For all interaction partners, the regions mediating binding to ALKBH4 comprised domains previously reported to be involved in interaction with DNA or chromatin. Furthermore, some of these partners showed nuclear co-localization with ALKBH4. However, the global gene expression pattern was only marginally altered upon ALKBH4 over-expression, and larger effects were observed in the case of ALKBH7. Although the molecular function of both proteins remains to be revealed, our findings suggest a role for ALKBH4 in regulation of gene expression or chromatin state.