Dynamic programming (DP) is not a useful tool for solving many control problems because of its complexity in computation. In this paper, we propose Approximate Dynamic Programming (ADP) optimal control strategy for ship course trajectory tracking control problems. Via system transformation, we convert the optimal tracking problem into designing a infinite-horizon optimal regulator for the tracking error dynamics. Action-dependent Heuristic Dynamic programming (ADHDP) technique, as one form of ADP, is presented to obtain the infinite-horizon optimal tracking controller. From the ship course optimal tracking control simulation results, we can see that the ADHDP controller makes the performance index and the control sequence for the error dynamics converge to the optimal values. Two BP neural networks are used as parametric structures to implement ADHDP algorithm. These two neural networks aim at approximating the cost function and the control law, respectively.