The main goal of this paper is to propose a numerical algorithm for solving a class of nonlinear parabolic integro-differential equations with nonlinear memory. The numerical method is based on the sixth-kind Chebyshev polynomials. The numerical approach is completely described and the convergence analysis of the method is presented. The effectiveness and the ability of the numerical scheme are investigated by solving a test problem.