This paper presents a novel motion estimation scheme for depth-map coding. Depth map has a couple of different characteristics compared with the common color scene, and therefore, careful investigation of the conventional fast motion search schemes is required. In this paper, I first provide the necessity of the depth-oriented motion search scheme based on experiments and then analyze the problems of the conventional methods. On the basis of the analysis, I propose to use the initial position refinement step during a motion search. In detail, the modification of the one-at-a-time search scheme is proposed for improvement of the prediction accuracy, and an initial direction selection and a 1-bit transform scheme follow for complexity reduction. The experimental results show that the proposed scheme can achieve coding gains of more than 3% on average over the state-of-the-art zonal search methods while keeping the overall complexity increase low.