Since Darwin's time, degree of ecological similarity between exotic and native species has been assumed to affect the establishment success or failure of exotic species. However, a direct test of the effect of exotic-native similarity on establishment of exotics is scarce because of the difficulty in recognizing failures of species to establish in the field. Here, using a database on the establishment success and failure of exotic fish species introduced into 673 freshwater lakes, we evaluate the effect of similarity on the establishment of exotic fishes by combining phylogenetic and functional information. We illustrate that, relative to other biotic and abiotic factors, exotic-native phylogenetic and functional similarities were the most important correlates of exotic fish establishment. While phylogenetic similarity between exotic and resident fish species promoted successful establishment, functional similarity led to failure of exotics to become established. Those exotic species phylogenetically close to, but functionally distant from, native fishes were most likely to establish successfully. Our findings provide a perspective to reconcile Darwin's naturalization conundrum and suggest that, while phylogenetic relatedness allows exotic fish species to pre-adapt better to novel environments, they need to possess distinct functional traits to reduce competition with resident native fish species.