We show that selective labeling of proteins with protonated amino acids embedded in a perdeuterated matrix, dubbed 'proton clouds', provides general access to long-range contacts between nonexchangeable side chain protons in proton-detected solid-state NMR, which is important to study protein tertiary structure. Proton-cloud labeling significantly improves spectral resolution by simultaneously reducing proton line width and spectral crowding despite a high local proton density in clouds. The approach is amenable to almost all canonical amino acids. Our method is demonstrated on ubiquitin and the beta-barrel membrane protein BamA.