Under shear, complex fluids often undergo instabilities leading to new flow patterns. Shear-banding is such a flow-induced instability, observed in many systems of various microstructures from surfactants and polymer solutions, to liquid crystal polymers, emulsions, granular materials and foams. It results from the coupling between the flow and the mesoscopic architecture of the system. The flow changes the structure of the fluid that feeds back on the flow itself. A spectacular consequence is a reorganization of the flow into two macroscopic shear-bands of different viscosities coexisting in the velocity gradient direction. In this scenario, the flow is supposed to be purely one-dimensional. Using flow visualizations in Couette geometry, we demonstrate, for a system of giant micelles that, in contrast with this classical picture, the banded state is unstable and evolves towards a three-dimensional flow. We show that vortices stacked along the vorticity direction develop concomitantly with interfacial undulations. These cellular structures are mainly localized in the induced band and their dynamics is fully correlated to that of the interface. As the control parameter increases, we observe a transition from a steady vortex flow to a state where pairs of vortices are continuoulsy created and destroyed. Normal stress effects are discussed as potential mechanisms driving the three-dimensional flow.