We demonstrate a new method for non-destructive imaging of laser-cooled atoms. This spatial heterodyne technique forms a phase image by interfering a strong carrier laser beam with a weak probe beam that passes through the cold atom cloud. The figure of merit equals or exceeds that of phase-contrast imaging, and the technique can be used over a wider range of spatial scales. We show images of a dark spot MOT taken with imaging fluences as low as 61 pJ/cm^2 at a detuning of 11 linewidths, resulting in 0.0004 photons scattered per atom.