General Gauss-Bonnet gravity with a cosmological constant allows two anti-de Sitter (AdS) spacetimes to be taken as its vacuum solutions. It is found that there is a critical point in the parameter space where the two AdS vacuums coalesce into one, which is very different from the general Gauss-Bonnet gravity. Susskind’s team proposed a Complexity/Action duality based on AdS/CFT duality, which provides a new method of studying the complexity of black holes. Fan and Liang (Fan Z Y, Liang H Z 2019 Phys. Rev. D 100086016) gave the formula of the evolution of complexity for general higher derivative gravity, and discussed the complexity evolution of the neutral planar Gauss-Bonnet-AdS black holes in detail by the numerical method. With the method of studying the complexity of general higher derivative gravity proposed by Fan and Liang (2019), we investigate the complexity evolution of critical neutral Gauss-Bonnet-AdS black holes, and compare these results with the results of the general neutral Gauss-Bonnet-AdS black holes, showing that the overall regularities of the evolution of the complexity of these two objects are consistent, and their main difference lies in the dimensionless critical time. As for the five-dimensional critical neutral Gauss-Bonnet-AdS black holes, when the event horizon of the black holes is flat or spherical, the dimensionless critical times of black holes with different sizes are identical, all reaching their minimum values. While in the higher dimensional cases, the differences in dimensionless critical time among spherically symmetric critical neutral Gauss-Bonnet-AdS black holes with different sizes are obviously less than those of general ones. These differences are probably related to the criticality of the neutral Gauss-Bonnet-AdS black holes.