Base excision DNA repair (BER) is an important process used by all living organisms to remove nonbulky lesions from DNA. BER is usually initiated by DNA glycosylases that excise a damaged base leaving an apurinic/apyrimidinic (AP) site, and an AP endonuclease then cuts DNA at the AP site, and the repair is completed by correct nucleotide insertion, end processing, and nick ligation. It has emerged recently that the BER machinery, in addition to genome protection, is crucial for active epigenetic demethylation in the vertebrates. This pathway is initiated by TET dioxygenases that oxidize the regulatory 5-methylcytosine, and the oxidation products are treated as substrates for BER. T:G mismatch-specific thymine-DNA glycosylase (TDG) and AP endonuclease 1 (APE1) catalyze the first two steps in BER-dependent active demethylation. In addition to the well-structured catalytic domains, these enzymes possess long tails that are structurally uncharacterized but involved in multiple interactions and regulatory functions. In this review, we describe the known roles of the tails in TDG and APE1, discuss the importance of order and disorder in their structure, and consider the evolutionary aspects of these accessory protein regions. We also propose that the tails may be important for the enzymes’ oligomerization on DNA, an aspect of their function that only recently gained attention.