Explicit numerical computations of super-fast differentially rotating disks are subject to the time-step constraint imposed by the Courant condition. When the bulk orbital velocity largely exceeds any other wave speed the time step is considerably reduced and a large number of steps may be necessary to complete the computation. We present a robust numerical scheme to overcome the Courant limitation by extending the algorithm previously known as FARGO (Fast Advection in Rotating Gaseous Objects) to the equations of magnetohydrodynamics (MHD). The proposed scheme conserves total angular momentum and energy to machine precision and works in Cartesian, cylindrical, or spherical coordinates. The algorithm is implemented in the PLUTO code for astrophysical gasdynamics and is suitable for local or global simulations of accretion or proto-planetary disk models. By decomposing the total velocity into an average azimuthal contribution and a residual term, the algorithm solves the MHD equations through a linear transport step in the orbital direction and a standard nonlinear solver applied to the MHD equations written in terms of the residual velocity. Since the former step is not subject to any stability restriction, the Courant condition is computed only in terms of the residual velocity, leading to substantially larger time steps. The magnetic field is advanced in time using the constrained transport method in order to preserve the divergence-free condition. Conservation of total energy and angular momentum is enforced at the discrete level by properly expressing the source terms in terms of upwind fluxes available during the standard solver. Our results show that applications of the proposed orbital-advection scheme to problems of astrophysical relevance provides, at reduced numerical cost, equally accurate and less dissipative results than standard time-marching schemes.