Vehicle slip is a critical issue for mobile robots driving across loose soil. It is responsible for gradual deviation of the vehicle from the intended course, resulting in large drift and poor performance of localization and control systems, even leading, in extreme cases, to the danger of vehicle entrapment with consequent mission failure. This paper presents a novel method for lateral slip estimation based on visually observing the trace produced by the wheels of the robot, during traverse of soft, deformable terrain, as that expected for lunar and planetary rovers. The proposed algorithm uses a robust Hough transform enhanced by fuzzy reasoning to estimate the angle of inclination of the wheel trace with respect to the vehicle reference frame. Any deviation of the wheel trace from the planned path of the robot suggests occurrence of sideslip that can be detected, and more interestingly, measured. This allows the vehicle to estimate its actual heading angle, usually referred to as the slip angle. The details of the various steps of the visual algorithm are presented and the results of experimental tests performed in the field with an all-terrain rover are described, proving the method to be effective and robust.