Searches for transient astrophysical sources often reveal unexpected classes of objects that are useful physical laboratories. In a recent survey for pulsars and fast transients, we have uncovered four millisecond-duration radio transients all more than 40 degrees from the Galactic plane. The bursts' properties indicate that they are of celestial rather than terrestrial origin. Host galaxy and intergalactic medium models suggest that they have cosmological redshifts of 0.5 to 1 and distances of up to 3 gigaparsecs. No temporally coincident x- or gamma-ray signature was identified in association with the bursts. Characterization of the source population and identification of host galaxies offers an opportunity to determine the baryonic content of the universe.