Most plants and animals reproduce sexually with individuals developing as either male or female and remaining the same sex throughout life. However, in some vertebrates, notably teleost fishes, individuals do not lose the potential of sexual plasticity during their life cycle. One of the most dramatic examples is functional sex change, which is widespread in many marine fishes. For example, the Caribbean bluehead wrasse (Thalassoma bifasciatum) displays socially-controlled female-to-male (protogynous) sex change that entails radical alterations at multiple levels, which include a complete ovary-to-testis transformation occurring in 1 to 2 weeks. The molecular basis underpinning such sexual plasticity remains poorly understood. Here we present the first global analysis of gonadal gene expression across protogynous sex change using RNA-sequencing approaches. Whole-transcriptome expression analysis in bluehead wrasses revealed a clear trend whereby many female-pathway genes were steadily down-regulated until mid sex-change stages when a male-specific expression network was progressively up-regulated. The gonadal aromatase gene that governs estrogen production was silenced prior to other feminizing genes, indicating that interruption of estrogen signaling is a key event initiating gonadal sex change. We also identified genes and pathways never before implicated in sex determination or differentiation in any vertebrate system, and interesting expression patterns of some key sex-related genes that indicate novel roles of these genes in regulating sex change. These results provide knowledge of how a usually committed developmental process remains plastic in sex-changing fishes, which is of fundamental importance for understanding sexual plasticity and the evolution of vertebrate sex determination and differentiation systems.