The propagation of a coronal mass ejection (CME) to the Earth takes between about 15 h and several days. We explore whether observations of non-thermal microwave bursts, produced by near-relativistic electons via the gyrosynchrotron process, can be used to predict travel times of interplanetary coronal mass ejections (ICMEs) from the Sun to the Earth. In a first step, a relationship is established between the CME speed measured by the Solar and Heliospheric Observatory/Large Angle and Spectro-metric Coronagraph (SoHO/LASCO) near the solar limb and the fluence of the microwave burst. This relationship is then employed to estimate speeds in the corona of earthward-propagating CMEs. These speeds are fed into a simple empirical inter-planetary acceleration model to predict the speed and arrival time of the ICMEs at Earth. The predictions are compared with observed arrival times and with the predictions based on other proxies, including soft X-rays (SXR) and coronographic measurements. We found that CME speeds estimated from microwaves and SXR predict the ICME arrival at the Earth with absolute errors of 11 ± 7 and 9 ± 7 h, respectively. A trend to underestimate the interplanetary travel times of ICMEs was noted for both techniques. This is consistent with the fact that in most cases of our test sample, ICMEs are detected on their flanks. Although this preliminary validation was carried out on a rather small sample of events (11), we conclude that microwave proxies can provide early estimates of ICME arrivals and ICME speeds in the interplanetary space. This method is limited by the fact that not all CMEs are accompanied by non-thermal microwave bursts. But its usefulness is enhanced by the relatively simple observational setup and the observation from ground, which makes the instrumentation less vulnerable to space weather hazards.