Planetary exploration is rapidly gaining importance within the space research community. Autonomous locomotion of rovers requires consideration of several mobility aspects to ensure safety, including avoiding hazardous areas that can cause the robot to become immobilized in soft soil or damaged in sharp terrains. Furthermore, when executing autonomous guidance, selecting an appropriate path to follow is crucial to reduce energy consumption and improve the overall distance traveled by the rover. This directly impacts the rover’s performance and the possible scientific outcome of the mission. This paper addresses the optimization of the autonomous locomotion of Mars rovers by acting on the guidance and control layers. Firstly, an enhanced velocity-based traction controller is proposed, permitting omnidirectional motion while simultaneously addressing slip and kinematic incompatibilities. The controller acts directly at the wheel command level to further improve traction and tracking performances, reducing position and heading errors. The performance metrics evaluated within the traction controller are then used to dynamically update the cost map of the environment. Finally, a higher-level path planner is integrated considering kino-dynamic constraints, continuously providing new paths according to the map updates. The proposed framework has been validated through simulation and real-world experiments on the MaRTA rover of ESA’s Planetary Robotics Laboratory. The results demonstrated that the proposed controller achieves better traction and tracking performance, further improved by the dynamic cost map updates.