Simultaneous measurements of internal structure, granular volume, and boundary shear force are reported for dense granular packings steadily sheared under a fixed normal load. We identify important consequences of the crystallization transition for deep flows, whose height-dependent local mean velocity spans more than five orders of magnitude. The structural change is accompanied by a significant decrease of granular volume and shear force, and dramatic change of the internal velocity field. Boundary conditions can have a profound influence on the crystallization of the entire layer. Furthermore, for given boundary conditions and long-term shearing, the evolution can depend on the prior history of the shearing process. A few cycles of initial oscillatory shearing can favor ordering, while compaction due to unidirectional shear can stabilize the disordered state. These experiments raise interesting questions about incorporating internal structure into theories of granular flow.