The rapid time variability of gamma-ray bursts implies the sources are very compact, and the peak luminosities are so high that some matter must be ejected at ultra-relativistic speeds. The very large Lorentz factors of the bulk flow are also indicated by the very broad and hard spectra. It is natural to expect that when the relativistic ejecta interact with the interstellar matter a strong synchrotron radio emission is generated, as is the case with supernova remnants and radio galaxies. We estimate that the strongest gamma-ray bursts may be followed by radio transients with peak fluxes as high as 0.1 Jy. The time of peak radio emission depends on the distance scale; it is less than a minute if the bursts are in the galactic halo, and about a week if the bursts are at cosmological distances