In this paper, we present a new numerical method based on the fractional-order Chelyshkov functions (FCHFs) for solving fractional variational problems (FVPs) and fractional optimal control problems (FOCPs). The fractional derivatives are considered in the Caputo sense. The operational matrix of fractional integral for FCHFs, together with the Lagrange multiplier method, are used to reduce the fractional optimization problem into a system of algebraic equations. Some results concerning the approximation errors are discussed and the convergence of the presented method is also demonstrated. The performance of the introduced method is tested through several examples. Some comparisons with recent numerical methods are introduced to show the accuracy and effectiveness of the presented method.