A modified orthogonal search (OS) algorithm via gradient descent is proposed for fast motion estimation (ME). Gradient descent method, a first-order optimization algorithm in machine learning, is employed in video coding to reduce the ME time for coding performance enhancement. An improved OS algorithm is created in our proposed method. Through this method, the number of search points is reduced significantly and lower computation time can be achieved. Experimental results demonstrate that the proposed method can greatly improve the coding performance of H.264/AVC.