We study the performance of adaptive Fourier-Galerkin methods in a periodic box in R d \mathbb {R}^d with dimension d ≥ 1 d\ge 1 . These methods offer unlimited approximation power only restricted by solution and data regularity. They are of intrinsic interest but are also a first step towards understanding adaptivity for the h p hp -FEM. We examine two nonlinear approximation classes, one classical corresponding to algebraic decay of Fourier coefficients and another associated with exponential decay typical of spectral approximation. We investigate the natural sparsity class for the operator range and find that the exponential class is not preserved, thus in contrast with the algebraic class. This entails a striking different behavior of the feasible residuals that lead to practical algorithms, influencing the overall optimality. The sparsity degradation for the exponential class is partially compensated with coarsening. We present several feasible adaptive Fourier algorithms, prove their contraction properties, and examine the cardinality of the activated sets. The Galerkin approximations at the end of each iteration are quasi-optimal for both classes, but inner loops or intermediate approximations are sub-optimal for the exponential class.