An efficient gyro-aided iterative Earth Mover's Distance (iEMD) algorithm for visual tracking is proposed in this paper. The Earth Mover's Distance (EMD) is used as the similarity measure to search the optimal template candidates in color-spatial space in a video sequence. The computation of the EMD is formulated as the transportation problem from linear programming. The efficiency of this optimization problem limits its use for visual tracking. To efficiently track a target, a monotonically convergent iterative optimization algorithm is developed. Based on the current location of the template candidate, the EMD is calculated and reformulated as the function of the weights of the template candidate. Then the derivative of the EMD with respect to the template displacement is calculated to search for the new position of the target. The iEMD tracking algorithm assumes small inter-frame movement in order to guarantee convergence. When the camera is mounted on a moving robot, e.g., a flying quadcopter, the camera could experience sudden and rapid motion leading to large inter-frame movements. In order to ensure that the tracking algorithm converges, synchronized gyroscope information is utilized to compensate for the rotation of the camera. Three publicly available datasets are used to validate the proposed algorithm. This algorithm is compared with the Mutual Information tracker and the kernel-based Mean-shift tracker by tracking an object undergoing severe illumination changes. The iEMD algorithm outperforms the others in terms of accuracy. The robustness of this algorithm to the ego-motion of the camera is also illustrated.