In this research, we study a general class of variable order integro-differential equations (VO-IDEs). We propose a numerical scheme based on the shifted fifth-kind Chebyshev polynomials (SFKCPs). First, in this scheme, we expand the unknown function and its derivatives in terms of the SFKCPs. To carry out the proposed scheme, we calculate the operational matrices depending on the SFKCPs to find an approximate solution of the original problem. These matrices, together with the collocation points, are used to transform the original problem to form a system of linear or nonlinear algebraic equations. We discuss the convergence of the method and then give an estimation of the error. We end by solving numerical tests, which show the high accuracy of our results.