Nuclear magnetic resonance imaging is used to study rates of sedimentation in several non-Newtonian fluids. It is shown that either shear thinning or elasticity in a fluid can result in a time-dependent sedimentation rate, as measured by the motion of the suspension-supernatant interface. Sedimentation is most rapid at the beginning of the process, and grows steadily slower in time. Two-dimensional images of vertical sections of suspension show clearly the development of a nonhomogeneous microstructure during sedimentation in a viscoelastic fluid. Elongated columns of particles form in the direction of gravity, and these columns are separated by comparably sized regions of pure fluid. Such structures are not present in sedimentation in Newtonian fluids, where the suspension microstructure is homogeneous for the duration of the process.