Context <p>Obtaining the global minimum in the potential energy hypersurface of nanoclusters is a very difficult task, due to the large number of degrees of freedom and the vast number of local minima. However, the discovery of such minima provides the geometrical arrangement that is more likely to occur, which is a key step in computing the properties of such particles. Here we developed a genetic algorithm (GA) including a gradient adjustment in each local optimization, to obtain an efficient GA, which is particularly useful when the algorithm is coupled with electronic structure methods. The idea is first validated, and then used to predict the minima of large sodium nanoclusters up to one hundred atoms.</p> Methods <p>To validate the algorithm, we analyzed its efficiency in obtaining the global minima of Lennard–Jones clusters, whose solutions are well known and can be used as benchmark. The new GA is compared to a random search and a standard GA. For exploring the potential energy surface of sodium clusters, we employ the Density-Functional Tight-Binding (DFTB) method, with parameters that have been tuned specifically to such clusters, thus enhancing its reliability for this specific application.</p>