Most empirical and numerical models of Interplanetary Coronal Mass Ejection (ICME) propagation use the initial CME velocity as their primary, if not only, observational input. These models generally predict a wide spread of 1 AU transit times for ICMEs with the same initial velocity. We use a 3D coupled MHD model of the corona and heliosphere to determine the ambient solar wind's effect on the propagation of ICMEs from 30 solar radii to 1 AU. We quantitatively characterize this deceleration by the velocity of the upstream ambient solar wind. The effects of varying solar wind parameters on the ICME transit time are quantified and can explain the observed spread in transit times for ICMEs of the same initial velocity. We develop an adjustment formula that can be used in conjunction with other models to reduce the spread in predicted transit times of Earth-directed ICMEs.