The evolution of texture and microstructure during warm rolling and subsequent annealing in aluminum 3004 alloy sheets was investigated by X-ray texture measurements and microstructure observations. Warm rolling at 250degreesC led to the development of strong through thickness texture gradients with shear textures at the surface layer and a regular rolling textures in the center of the sheets. FEM simulations indicated that these texture gradients are caused by pronounced strain gradients throughout the sheet thickness. Upon recrystallization annealing, in the sheet center the characteristic cube-recrystallization texture developed, while in the surface layers with a pronounced shear texture continuous recrystallization took place which led to the formation of a very fine grained microstructure. It is concluded that the very complex strain history in the near-surface layers together with the resulting high work-hardening rate gave rise to the formation of the ultra-fine grains with an average size smaller than 2 mum.