This paper focuses on the numerical solution of fractional variational problems using fractional-order Chelyshkov functions. First, a set of orthonormal fractional-order basis functions is introduced based on the definition of Chelyshkov polynomials. Then, the Riemann-Liouville fractional integrals of these basis functions are computed. This result, combined with the properties of the Riemann-Liouville integral and the Caputo fractional derivative, as well as the Gauss-Legendre quadrature formula, provides an approximation for the functional of the problem. The Lagrange multiplier method and the necessary optimality conditions yield an approximation of the solution. Finally, an example and its numerical results are presented to demonstrate the efficiency and accuracy of the method.