Nonlinear optimal control problems governed by variable-order fractional integro-differential equations constitute an important subgroup of optimal control problems. This group of problems is often difficult or impossible to solve analytically because of the variable-order fractional derivatives and fractional integrals. In this article, we utilized the expansion of Lagrange polynomials in terms of Chebyshev polynomials and the power series of Chebyshev polynomials to find an approximate solution with high accuracy. Subsequently, by employing collocation points, the problem was transformed into a nonlinear programming problem. In addition, variable-order fractional derivatives in the Caputo sense were represented by a new operational matrix, and an operational matrix represented fractional integrals. As a result, the mentioned integro-differential optimal control problem becomes a nonlinear programming problem that can be easily solved with the repetitive optimization method. In the end, the proposed method is illustrated by numerical examples that demonstrate its efficiency and accuracy.