Electron backscatter diffraction was used to study grain structure development in heavily cryogenically-rolled Cu-30%Zn brass. The produced microstructure was found to be very inhomogeneous. At a relatively coarse scale, it consisted of texture bands having crystallographic orientations close to the α- and γ-fibers. The texture bands contained internal structure comprising shear bands, mechanical twins, and low-angle boundaries. Such features were more pronounced within the γ-fiber, and this resulted in a heterogeneous ultrafine grain structure. The cryogenic rolling was concluded to be not straightforward for production of nanocrystalline grain structure in Cu-30%Zn brass.