By combining a background feature block matching and a histogram clustering method, a new approach for stabilizing videos with moving objects was proposed. The estimated global motion parameters were used to compensate the inter-frame camera motion,and a frame differencing method was adopted to segment the foreground and background blocks, then the feature blocks on the background of reference frame were matched with that on the current frame to estimate the global motion in the next run. By using a one-block-to-multiple-block matching strategy, the reference feature block was matched with the feature blocks of the current frame in the search window centered on the reference block, thus a sparse motion vector field was built. Then, the un-removed foreground vectors and erroneous vectors in this vector field were filtered out using a histogram clustering method. The proposed approach has been tested by using many real videos with moving objects and compared with other state-of-the-art video stabilization algorithms and techniques. The results indicate that the proposed approach can achieve an inter-frame transformation fidelity value by 31.05 dB, which is as high as those of state-of-the-art algorithms and techniques. Moreover, it has a higher robustness to moving objects and can remove inter-frame high frequency jitters and improve video quality.