Since Darwin’s time, the 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 establishment of exotic fishes by combining the phylogenetic and functional information. We illustrate that exotic-native phylogenetic and functional similarities were the most important correlates of successful establishment relative to other biotic and abiotic factors. Those exotic species phylogenetically close to, but functionally distant from, native fishes were most likely to establish successfully. Our results 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 fish species.