The Escherichia coli DNA repair enzyme AlkB is a 2-oxoglutarate (2OG)-dependent Fe(2+) binding dioxygenase that removes methyl lesions from DNA and RNA. To date, nine human AlkB homologues are known: ABH1 to ABH8 and the obesity-related FTO. Similar to AlkB, these homologues exert their activity on nucleic acids, although for some homologues the biological substrate remains to be identified. 2OG dioxygenases require binding of the cofactors Fe(2+) and 2OG in the active site to form a catalytically competent complex. We present a structural analysis of AlkB using NMR, fluorescence, and CD spectroscopy to show that AlkB is a dynamic protein exhibiting different folding states. In the absence of the cofactors Fe(2+) and 2OG, apoAlkB is a highly dynamic protein. Binding of either Fe(2+) or 2OG alone does not significantly affect the protein dynamics. Formation of a fully folded and catalytically competent holoAlkB complex only occurs when both 2OG and Fe(2+) are bound. These findings provide the first insights into protein folding of 2OG-dependent dioxygenases. A role for protein dynamics in the incorporation of the metal cofactor is discussed.