It has recently been shown that a rapidly rotating Newtonian star can spin up by radiating angular momentum. Extremely fast pulsars losing energy and angular momentum by magnetic dipole radiation or gravitational radiation may exhibit this behavior. Here, we show that this phenomenon is more widespread for rapidly rotating stars in general relativity. We construct and tabulate polytropic sequences of fully relativistic rotating stars of constant rest mass and entropy. We find that the range of adiabatic indices allowing spin-up extends somewhat above 4/3 because of the nonlinear effects of relativistic gravity. In addition, there is a new class of 'supramassive' stars which will inevitably spin up by losing angular momentum regardless of their equation of state. A supramassive star, spinning up via angular momentum loss, will ultimately evolve until it becomes unstable to catastrophic collapse to a black hole. Spin-up in a rapidly rotating star may thus be an observational precursor to such collapse.