Spin-triplet superconductors potentially host topological excitations that are of interest for quantum information processing. We report the discovery of spin-triplet superconductivity in UTe2, featuring a transition temperature of 1.6 kelvin and a very large and anisotropic upper critical field exceeding 40 teslas. This superconducting phase stability suggests that UTe2 is related to ferromagnetic superconductors such as UGe2, URhGe, and UCoGe. However, the lack of magnetic order and the observation of quantum critical scaling place UTe2 at the paramagnetic end of this ferromagnetic superconductor series. A large intrinsic zero-temperature reservoir of ungapped fermions indicates a highly unconventional type of superconducting pairing.