Males and females often display extensive phenotypic differences, and many of these sexual dimorphisms are thought to result from differences between males and females in expression of genes present in both sexes. Sex-biased genes have been shown to exhibit accelerated rates of evolution in a wide array of species, however the cause of this remains enigmatic. In this study, we investigate the extent and evolutionary dynamics of sex-biased gene expression in zebrafish. Our results indicate that both male-biased genes and female-biased genes exhibit accelerated evolution at the protein level. In order to differentiate between adaptive and nonadaptive causes, we tested for codon usage bias and signatures of different selective regimes in our sequence data. Our results show that both male-and female-biased genes show signatures consistent with adaptive evolution. In order to test the generality of our findings across fish, we also analyzed publicly available data on sticklebacks, and found results consistent with our findings in zebrafish.