The thermal stability of nanocrystalline cartridge brass (Cu-30 at.% Zn) and brass-Zr alloys were investigated. The alloys were produced by cryogenic ball milling and subsequently heat treated to a maximum temperature of 800 A degrees C. The grain size of pure brass was found to be relatively stable in comparison to pure copper, and a high hardness was retained up to 600 A degrees C. When 1 at.% zirconium was alloyed with the brass, the grain size was stabilized near 100 nm even at 800 A degrees C. At the highest temperature, hardness was retained above 2.5 GPa for 1 and 5 at.% zirconium alloys, but the pure brass softened significantly. The stabilization is believed to be dominated by Zn-Zr interactions as a second phase of these two was observed in X-ray diffraction and transmission electron microscopy. Thermodynamic modeling indicates a zero grain boundary energy may be achieved depending on the mixing enthalpy value used (i.e., calculated vs. experimental) under ideal conditions, but microstructural features such as twinning and second phase particles are thought to be the dominant stabilization mechanism. Zr worked well in stabilizing the brass in the nanocrystalline state to nearly 90 % of its melting temperature.