Provision of variable block sizes and multiple reference frames in motion estimation (ME) significantly improves the compression efficiency of H.264. The involved computation for finding the best reference picture and ME mode in the rate-distortion minimization sense, however, is usually intimidating. In this paper, a new H.264 fast inter- mode decision algorithm is presented. The proposed method employs the coded block patterns, correlated modes and rate-distortion costs to avoid exhaustive mode evaluation. Specific values of coded block patterns, which reflect the accuracy of 16x16 ME, are used to identify whether large partitioning blocks are suitable. Inter-frame correlation in terms of modes and rate-distortion costs, is further incorporated for fast mode decision. Accuracy of the proposed expediting criteria is verified through comprehensive evaluations. Compared with state-of-the-art fast mode-decision algorithms, the proposed method achieves consistently more time savings with little sacrifice in bit rate. In addition to the reduction in computational complexity, the proposed method is elegant without any ad-hoc thresholds.