In this paper, the alternative Legendre polynomials (ALPs) are used to approximate the solution of a class of nonlinear multi-order fractional differential equations (FDEs). First, the operational matrix of fractional integration of an arbitrary order and the product operational matrix are derived for ALPs. These matrices together with the spectral Tau method are then utilized to reduce the solution of the mentioned equations into the one of solving a system of nonlinear algebraic equations with unknown ALP coefficients of the exact solution. The fractional derivatives are considered in the Caputo sense and the fractional integration is described in the Riemann-Liouville sense. Numerical examples illustrate that the present method is very effective for linear and nonlinear multi-order FDEs and high accuracy solutions can be obtained only using a small number of ALPs.