Pure nanostructured materials are unstable against grain growth, but the additional of second elements can greatly stabilize these fine grain sizes. This improvement can come from planned dopants that reduce grain boundary energy, or even impurities from the fabrication routes used to make the nanostructured materials. In this talk, we describe how both metallic dopants and nonmetal impurities affect the mechanical behavior of grain boundaries. First, we study how grain boundary doping interacts with the deformation mechanisms that control the strength of nanocrystalline metals, using both experimental and computational techniques. Both ordered grain boundary structures and amorphous intergranular films are reported on, to connect to recent reports on hierarchical nanostructured materials. In addition, first-principles calculations and experimental data are used to study the effect of common nonmetal impurities on grain boundary deformation, with a focus on avoiding any embrittling effects.