This paper presents a novel hybrid technique based on the modal series method and linear programming strategy for solving the optimal control problem of nonlinear fractional-order systems. The fractional derivative is defined in the sense of Riemann-Liouville with order less than one. The performance index includes the terminal cost in addition to the integral quadratic cost functional. Both the fixed and free final states cases have been taken into account. In this approach, first we extend the modal series method in order to convert the original nonlinear fractional-order two point boundary value problem (FTPBVP) derived from the Pontryagin’s maximum principle into a sequence of linear time-invariant FTPBVPs. This sequence is then transformed into a sequence of linear programming problems by defining a new variational problem in the calculus of variations, using a discretization technique based on the first-order Grünwald-Letnikov approximation and introducing a new transformation. The convergence analysis of the proposed approach is also provided. To achieve an accurate suboptimal control, we apply a fast iterative algorithm with low computational effort. Finally, two numerical examples are included to illustrate the effectiveness of the proposed approach.