Detailed (gas-phase) MP2/6-31G*(0.25) potential energy surface scans and CCSD(T) energy calculations at the complete basis set (CBS) limit were used to analyze the (face-to-face) stacking and (edge-to-face) T-shaped interactions between histidine (modeled as imidazole) and the DNA nucleobases. For the first time, a variety of relative monomer arrangements between both neutral and protonated histidine and the natural nucleobases were considered to determine the effects of charge on the optimum dimer geometry and binding strength. Our results reveal that protonation of histidine changes the preferred relative orientations of the monomers and propose that these geometric differences may be combined with experimental crystal structures to assess the protonation state of histidine in different environments. It is also found that protonation affects the nucleobase binding preference, as well as the magnitude of the stacking and T-shaped interactions. Indeed, the maximum possible stacking and T-shaped interactions involving the neutral histidine range between approximately 20 and 45 kJ mol(-1), while this range increases to 40-105 kJ mol(-1) upon protonation, which represents an up to 330% enhancement. Although an increase in the interaction energies upon protonation of histidine is expected, the present work provides a measure of the magnitude of this enhancement in the gas phase and reveals that the amplification is almost entirely due to larger electrostatic contributions. The relative strengthening of different classifications of dithers upon protonation leads to stronger T-shaped interactions than stacking energies for protonated histidine, while the stacking and T-shaped interactions involving neutral histidine are of comparable magnitude. Thus, there is,a significant difference in the nature of the pi(cation)-pi interactions involving protonated histidine and the pi-pi interactions involving neutral histidine. The calculated strengths of the interactions studied in the present work suggest that both neutral and cationic histidine contacts will provide significant stabilization to DNA-protein complexes. Although solvation effects will decrease the magnitude of the reported interactions, our results are applicable to a variety of low-polarity, biologically-relevant environments such as nonpolar enzyme active sites. Therefore, our calculations suggest that these interactions may also be important for many biological processes. The proposed significance of these interactions is supported by the large number of histidine-nucleobase contacts that appear in experimental crystal structures. The highly accurate (MP2/6-31G*(0.25)) preferred structures and (CCSD(T)/CBS) binding strengths reported in the present work can be used as benchmarks to analyze the performance of existing, or to develop new, molecular mechanics force fields for use in large-scale molecular dynamics (MD) studies of DNA-protein complexes.