Two new orthogonal functions named the left- and the right-shifted fractional-order Legendre polynomials (SFLPs) are proposed. Several useful formulas for the SFLPs are directly generalized from the classic Legendre polynomials. The left and right fractional differential expressions in Caputo sense of the SFLPs are derived. As an application, it is effective for solving the fractional-order differential equations with the initial value problem by using the SFLP tau method.