A large international effort is nowadays devoted to increase the energy of the extreme ultraviolet pulses by using high-peak power ultrashort fundamental pulses (Terawatt level). Using such fundamental pulses brings specific constraints that need to be addressed. Here we study high-order harmonic generation in gases with 10 fs pulses at Terawatt peak power and demonstrate that extreme ultraviolet beams can be highly structured and complex in various conditions. We use a single-shot spatially resolved spectral detection and demonstrate direct observation of the spatio-temporal coupling occurring in the generating medium. Clear and reproducible complex spatio-spectral structures are observed in the far field. Similar structures are reproduced with simulations and we show that they are intimately associated to the high nonlinearity of high-order harmonic generation. Those findings are of prime importance for the generation of high-energy attosecond pulses and reveal important issues for their applications.