Collimated relativistic outflows-also known as jets-are amongst the most energetic phenomena in the Universe. They are associated with supermassive black holes in distant active galactic nuclei, accreting stellar-mass black holes and neutron stars in binary systems and are believed to be responsible for gamma-ray bursts. The physics of these jets, however, remains something of a mystery in that their bulk velocities, compositions and energetics remain poorly determined. Here we report the discovery of an ultra-relativistic outflow from a neutron star accreting gas within a binary stellar system. The velocity of the outflow is comparable to the fastest-moving flows observed from active galactic nuclei, and its strength is modulated by the rate of accretion of material onto the neutron star. Shocks are energized further downstream in the flow, which are themselves moving at mildly relativistic bulk velocities and are the sites of the observed synchrotron emission from the jet. We conclude that the generation of highly relativistic outflows does not require properties that are unique to black holes, such as an event horizon.