In this paper, we address the problems of camera pose estimation accuracy and runtime efficiency by incorporating an elite selection method and a voting system to a conventional visual odometry (VO) method, called the “enhanced VO algorithm”. The use of elite selection method improves the efficiency of perspective-3-point (P3P) algorithm by only employing an elite subset of landmarks to estimate the camera pose. The proposed voting system, on the other hand, provides reliable consensus set derived from random sample consensus (RANSAC) algorithm such that accuracy of camera pose estimations can be increased. To verify the performances of the proposed approach, we conducted various experiments using a Kinect RGB-D sensor, and the results show that the proposed VO system performs well in terms of not only estimation accuracy but also computational time.