The Discrete Moser-Veselov algorithm is an integrable discretisation of the equations of motion for the free rigid body. It is symplectic and time-reversible, and it conserves all first integrals of the system. The only drawback is its low order. We present a modification of this algorithm to arbitrarily high order which has negligeable overhead but considerably improves the accuracy.