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{\deg} 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. ; Comment: 20 pages, 6 figures, 2 tables. Energies in table 1 corrected from hard-copy version