Despite the ability to image coronal mass ejections (CMEs) from the Sun through the inner heliosphere, the forecasting of their Time-of-Arrival (ToA) to Earth does not yet meet most Space weather users’ requirements. The main physical reason is our incomplete understanding of CME propagation in the inner heliosphere. Therefore, many ToA forecasting algorithms rely on simple empirical relations to represent the interplanetary propagation phase using, mostly, kinematic information from coronagraphic observations below 30 solar radii (Rs) and a couple rather implying assumptions of constant direction and speed for the transient. Here, we explore a different, yet still empirical approach. We replace the assumption of constant speed in the inner heliosphere with a two-phase behavior consisting of a decelerating (or accelerating) phase from 20 Rs to some distance, followed by a coasting phase to Earth. In a nod towards a forecasting scheme, we consider only Earth-directed CMEs use kinematic measurements only from the Heliospheric Imagers aboard both STEREO spacecraft, treat each spacecraft separately to increase the event statistics, analyze the measurements in a data-assimilative fashion and intercompare them against three popular localization schemes for single viewpoint observations (fixed-φ, harmonic mean and self-similar expansion. For the 21 cases, we obtain the best mean absolute error (MAE) of 6.4±1.9 hours, for the harmonic mean approximation. Remarkably, the difference between predicted and observed ToA is < 52 minutes for 42% of the cases. We find that CMEs continue to decelerate beyond even 0.7 AU, in some cases.