Recent advances in gene editing have been enabled by programmable nucleases such as transcription activator-like effector nucleases (TALENs) and CRISPR-Cas9. However, several open questions remain regarding the molecular machinery in these systems, including fundamental search and binding behavior as well as role of off-target binding and specificity. In order to achieve efficient and specific cleavage at target sites, a high degree of target site discrimination must be demonstrated for gene editing applications. In this work, we studied the binding affinity and specificity for a series of TALE proteins under a variety of solution conditions using in vitro fluorescence methods and molecular dynamics (MD) simulations. Remarkably, we identified that TALEs demonstrate high sequence specificity only upon addition of small amounts of certain divalent cations (Mg2+, Ca2+). However, under purely monovalent salt conditions (K+, Na+), TALEs bind to specific and non-specific DNA with nearly equal affinity. Divalent cations preferentially bind to DNA over monovalent cations, which attenuates non-specific interactions between TALEs and DNA and further stabilizes specific interactions. Overall, these results uncover new mechanistic insights into the binding action of TALEs and further provide potential avenues for engineering and application of TALE- or TALEN-based systems for genome editing and regulation.