The H.264 video coding standard exhibits higher performance compared to the other existing standards such as H.263, MPEG-X. This improved performance is achieved mainly due to the multiple-mode motion estimation and compensation. Recent research tried to reduce the computational time using the predictive motion estimation, early zero motion vector detection, fast motion estimation, and fast mode decision, etc. These approaches reduce the computational time substantially, at the expense of degrading image quality and/or increase bitrates to a certain extent. In this paper we use phase correlation to capture the motion information between the current and reference blocks and then devise an algorithm for direct motion estimation mode prediction, without excessive motion estimation. A bigger amount of computational time is reduced by the direct mode decision and exploitation of available motion vector information from phase correlation. The experimental results show that the proposed scheme outperforms the existing relevant fast algorithms, in terms of both operating efficiency and video coding quality. To be more specific, 82~92% of encoding time is saved compared to the exhaustive mode selection (against 58~74% in the relevant state-of-the-art), and this is achieved without jeopardizing image quality (in fact, there is some improvement over the exhaustive mode selection at mid to high bit rates) and for a wide range of videos and bitrates (another advantages over the relevant state-of-the-art).