High-resolution electron backscatter diffraction (EBSD) was used to study grain structure development during cryogenic rolling of Cu-29.5Zn brass. Microstructure evolution was found to be broadly similar to that occurring during rolling at room temperature. Specifically, favorably-oriented grains (Copper {1 1 2} 〈1 1 1〉 and S {1 2 3}〈6 3 4〉) experienced profuse deformation twinning followed by extensive shear banding. This eventually produced an ultrafine structure with a mean grain size of ∼0.2 μm. On the other hand, grains with crystallographic orientations close to Brass {1 1 0}〈1 1 2〉 and Goss {1 1 0}〈1 0 0〈 were found to be stable against twinning/shear banding and thus showed no significant grain refinement. As a result, the final structure developed in heavily-rolled material was distinctly inhomogeneous consisting of mm-scale remnants of original grains with poorly developed substructure and ultra-fine grain domains.