This paper proposes a low bit-rate video coding scheme based on combination of motion compensation and waveform coding. In order to realize appropriate bit-allocation to both motion compensation and waveform coding according to the structural properties of video signals, we employ matching pursuits which can freely control a coding rate of motion compensated frame differences. Moreover we develop a new iterative motion compensation method which can also control a bit-rate flexibly and can successively improve quality of reconstructed images, and combine it with the above matching pursuits seamlessly and adaptively. In other words, motion compensation and matching pursuits are carried out alternatively and repeatedly to attain higher coding performance within a limited coding rate. Simulation results indicate that the proposed coding scheme shows SNR gains of 0.3-1.0 dB over the H.263 standard and provides visually better reconstructed images with less blocking artifacts than it.