Identifying new binding forces between electron donor and acceptor entities is key to properly understanding molecular recognition and aggregation phenomena, which are of inmense importance to biology. For decades, the halogenation of DNA/RNA bases has been routinely carried out to solve solid state structures of nucleic acids (NA). However, the effects of this modification might be deeper than just a simple atom substitution since halogens are also known to undergo noncovalent binding (halogen bonding). Herein we show that halogenated NAs with either Br or I atoms are able to establish halogen bonds with properly disposed protein residues. An inspection of the Protein Data Bank (PDB) reveals several examples involving 5-iodo/5-bromouracil, 8-bromoadenine, and 5-iodocytosine bases that are consistent with the halogen bond geometry features. Computations reveal the favorable and moderately strong nature of this interaction, thus confirming the ability of halogenated bases to actively participate in protein-NA binding.