Action across long distances on chromatin is a hallmark of eukaryotic transcriptional regulation. Although chromatin structure per se can support long-range interactions, the mechanisms of efficient communication between widely spaced DNA modules in chromatin remain a mystery. The molecular simulations described herein suggest that transient binary internucleosomal interactions can mediate distant communication in chromatin. Electrostatic interactions between the N-terminal tails of the core histones and DNA enhance the computed probability of juxtaposition of sites that lie far apart along the DNA sequence. Experimental analysis of the rates of communication in chromatin constructs confirms that long-distance communication occurs efficiently and independently of distance on tail-containing, but not on tailless, chromatin. Taken together, our data suggest that internucleosomal interactions involving the histone tails are essential for highly efficient, long-range communication between regulatory elements and their targets in eukaryotic genomes.