Standard evolutionary theories of aging postulate that reduced extrinsic mortality leads to evolution of longevity. Clownfishes of the genus Amphiprion live in a symbiotic relationship with sea anemones that provide protection from predators. We performed a survey and identified at least two species with a lifespan of over 20 years. Given their small size and ease of captive reproduction, clownfish lend themselves as experimental models of exceptional longevity. To identify genetic correlates of exceptional longevity, we sequenced the transcriptomes of Amphiprion percula and A. clarkii and performed a scan for positively-selected genes (PSGs). The PSGs that we identified in the last common clownfish ancestor were compared with PSGs detected in long-lived mole rats and short-lived killifishes revealing convergent evolution in processes such as mitochondrial biogenesis. Among individual genes, the Mitochondrial Transcription Termination Factor 1 (MTERF1), was positively-selected in all three clades, whereas the Glutathione S-Transferase Kappa 1 (GSTK1) was under positive selection in two independent clades. For the latter, homology modelling strongly suggested that positive selection targeted enzymatically important residues. These results indicate that specific pathways were recruited in independent lineages evolving an exceptionally extended or shortened lifespan and point to mito-nuclear balance as a key factor.