The maximally diverse grouping problem requires finding a partition of a given set of elements into a fixed number of mutually disjoint subsets (or groups) in order to maximize the overall diversity between elements of the same group. In this paper we develop a new variant of variable neighborhood search for solving the problem. The extensive computational results show that our new heuristic significantly outperforms the current state of the art. Moreover, the best known solutions have been improved on 531 out of 540 test instances from the literature.