Based on the navigation practice, the A* algorithm was improved to achieve the coordinated optimization of the course and speed of the ship throughout the voyage, which can ensure that the ship can complete the navigation task more safely and energyefficient by reasonably configuring the route and speed. Firstly, a dynamic sea area model with complex weather was established by using meteorological and hydrological data sets, and the navigable area and restricted area of the ship were delineated based on the actual situation of the ship. Secondly, speed optimization was added to the optimization link. With ship position, speed and sailing time as the optimization variables, the navigation cost was comprehensively evaluated by the standardized method based on the navigation fuel consumption and sailing time, and a collaborative optimization model of ship course and speed was constructed. Finally, in order to meet the navigation task with low fuel consumption and time, the model was simulated and solved by improving the evaluation function and operation steps of A* algorithm. The simulation results of navigation planning in the North Pacific region show that, compared with the big circle route, the proposed method can ensure that ships can effectively avoid the big wind and waves while reducing fuel consumption, and navigation decisions are more flexible, and can adapt to complex and changeable ocean navigation tasks.