A spectral method based on operational matrices of the second kind Chebyshev polynomials (SKCPs) is employed for solving fractional integro-differential equations with weakly singular kernels. Firstly, properties of shifted SKCPs, operational matrix of fractional integration and product operational matrix are introduced and then utilized to reduce the given equation to the solution of a system of linear algebraic equations. This new approach provides a significant computational advantage by converting the given original problem to an equivalent linear Volterra integral equation of the second kind with the same initial conditions. Approximate solution is achieved by expanding the functions in terms of SKCPs and employing operational matrices. Unknown coefficients are determined by solving final system of linear equations. An estimation of the error is given. Finally, illustrative examples are included to demonstrate the high precision, fast computation and good performance of the new scheme.