New, efficient reconstruction procedures are proposed for sensitivity encoding (SENSE) with arbitrary k-space trajectories. The presented methods combine gridding principles with so-called conjugate-gradient iteration. In this fashion, the bulk of the work of reconstruction can be performed by fast Fourier transform (FFT), reducing the complexity of data processing to the same order of magnitude as in conventional gridding reconstruction. Using the proposed method, SENSE becomes practical with nonstandard k-space trajectories, enabling considerable scan time reduction with respect to mere gradient encoding. This is illustrated by imaging simulations with spiral, radial, and random k-space patterns. Simulations were also used for investigating the convergence behavior of the proposed algorithm and its dependence on the factor by which gradient encoding is reduced. The in vivo feasibility of non-Cartesian SENSE imaging with iterative reconstruction is demonstrated by examples of brain and cardiac imaging using spiral trajectories. In brain imaging with six receiver coils, the number of spiral interleaves was reduced by factors ranging from 2 to 6. In cardiac real-time imaging with four coils, spiral SENSE permitted reducing the scan time per image from 112 ms to 56 ms, thus doubling the frame-rate. Copyright 2001 Wiley-Liss, Inc.