The Radiation Assessment Detector (RAD) instrument onboard the Mars Science Laboratory (MSL) mission’s Curiosity rover has been measuring galactic cosmic rays (GCR) as well as solar energetic particles (SEP) on the surface of Mars for more than 6 years since its landing in August 2012. The observations include a large number of Forbush decreases (FD) caused by interplanetary coronal mass ejections (ICMEs) and/or their associated shocks shielding away part of the GCR particles with their turbulent and enhanced magnetic fields while passing Mars. This study combines MSL/RAD FD measurements and remote tracking of ICMEs using the Solar TErrestrial RElations Observatory (STEREO) Heliospheric Imager (HI) telescopes in a statistical study for the first time. The large data set collected by HI makes it possible to analyze 149 ICMEs propagating toward MSL both during its 8-month cruise phase and after its landing on Mars. We link 45 of the events observed at STEREO-HI to their corresponding FDs at MSL/RAD and study the accuracy of the ICME arrival time at Mars predicted from HI data using different methods. The mean differences between the predicted arrival times and those observed using FDs range from −11–5 hr for the different methods, with standard deviations between 17 and 20 hr. These values for predictions at Mars are very similar compared to other locations closer to the Sun and also comparable to the precision of some other modeling approaches.