The evolution of insect male genitalia has received much attention, but there is still a lack of data on the macroevolutionary origin of its extraordinary variation. We used a calibrated molecular phylogeny of 71 of the 150 known species of the beetle genus Limnebius to study the evolution of the size and complexity of the male genitalia in its two subgenera, Bilimneus , with small species with simple genitalia, and Limnebius s.str., with a much larger variation in size and complexity. We reconstructed ancestral values of complexity (perimeter and fractal dimension of the aedeagus) and genital and body size with Bayesian methods. Complexity evolved more in agreement with a Brownian model, although with evidence of weak directional selection to a decrease or increase in complexity in the two subgenera respectively, as measured with an excess of branches with negative or positive change. On the contrary, aedeagus size, the variable with the highest rates of evolution, had a lower phylogenetic signal, without significant differences between the two subgenera in the average change of the individual branches of the tree. Aedeagus size also had a lower correlation with time and no evidence of directional selection. Rather than to directional selection, it thus seems that the higher diversity of the male genitalia in Limnebius s.str. is mostly due to the larger variance of the phenotypic change in the individual branches of the tree for all measured variables.