In this letter, we propose a novel manifold-based algorithm to solve the constant envelope (CE) precoding problem with interference exploitation. For a given power budget, we design the precoded symbols subject to the CE constraints, such that the constructive effect of the multi-user interference (MUI) is maximized. While the objective for the original problem is non-differentiable on the complex plane, we consider the smooth approximation of its real representation, and map it onto a Riemannian manifold. By using the Riemmanian conjugate gradient (RCG) algorithm, a local minimizer can be efficiently found for the problem. The complexity of the algorithm is analytically derived in terms of floating-points operations (flops) per iteration. Numerical results show that the proposed algorithm outperforms the conventional methods on both symbol error rate and computational complexity.