The discovery of new materials that efficiently transmit spin currents has been important for spintronics and material science. The electric insulator Gd3Ga5O12 (GGG), a standard substrate for growing magnetic films, can be a spin current generator, but has never been considered as a superior conduit for spin currents. Here we report spin current propagation in paramagnetic GGG over several microns. Surprisingly, spin transport persists up to temperatures of 100 K >> T-g = 180 mK, the magnetic glass-like transition temperature of GGG. At 5 K and 3.5 T, we find a spin diffusion length lambda(GGG) = 1.8 +/- 0.2 mu m and a spin conductivity sigma(GGG) = (7.3 +/- 0.3) x 10(4) Sm-1 that is larger than that of the record quality magnet Y3Fe5O12 (YIG). We conclude that exchange stiffness is not required for efficient spin transport, which challenges conventional models and provides new material-design strategies for spintronic devices.