The fundamental repeat unit of chromatin, the nucleosome, consists of approximately 147 base pairs of double-stranded DNA and a histone protein octamer containing two copies each of histones H2A, H2B, H3, and H4. Each histone possesses a dynamically disordered N-terminal tail domain, and it is well-established that the tails of histones H3 and H4 play key roles in chromatin compaction and regulation. Here we investigate the conformational ensemble and interactions of the H4 tail in nucleosomes by means of solution NMR measurements of paramagnetic relaxation enhancements (PREs) in recombinant samples reconstituted with 15N-enriched H4 and nitroxide spin-label tagged H3. The experimental PREs, which report on the proximities of individual H4 tail residues to the different H3 spin-label sites, are interpreted by using microsecond time-scale molecular dynamics simulations of the nucleosome core particle. Collectively, these data enable improved localization of histone H4 tails in nucleosomes and support the notion that H4 tails engage in a fuzzy complex interaction with nucleosomal DNA.