Proton-rich material in a state of nuclear statistical equilibrium (NSE) is one of the least studied regimes of nucleosynthesis. One reason for this is that after hydrogen burning, stellar evolution proceeds at conditions of equal number of neutrons and protons or at a slight degree of neutron-richness. Proton-rich nucleosynthesis in stars tends to occur only when hydrogen-rich material that accretes onto a white dwarf or neutron star explodes, or when neutrino interactions in the winds from a nascent proto-neutron star or collapsar-disk drive the matter proton-rich prior to or during the nucleosynthesis. In this paper we solve the NSE equations for a range of proton-rich thermodynamic conditions. We show that cold proton-rich NSE is qualitatively different from neutron-rich NSE. Instead of being dominated by the Fe-peak nuclei with the largest binding energy per nucleon that have a proton to nucleon ratio close to the prescribed electron fraction, NSE for proton-rich material near freeze-out temperature is mainly composed of Ni56 and free protons. Previous results of nuclear reaction network calculations rely on this non-intuitive high proton abundance, which this paper will explain. We show how the differences and especially the large fraction of free protons arises from the minimization of the free energy as a result of a delicate competition between the entropy and the nuclear binding energy.