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 {112}<111> and S {123}<634>) 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 {110}<112> and Goss {110}<100> 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.