We use the Bogoliubov-de Gennes formalism to analyze the effects of rotation on the ground-state phases of harmonically trapped Fermi gases, under the assumption that quantized vortices are not excited. We find that the rotation breaks Cooper pairs that are located near the trap edge, and that this leads to a phase separation between the nonrotating superfluid (fully paired) atoms located around the trap center and the rigidly rotating normal (nonpaired) atoms located toward the trap edge, with a coexistence (partially paired) region in between. Furthermore, we show that the superfluid phase that occurs in the coexistence region is characterized by a gapless excitation spectrum, and that it is distinct from the gapped phase that occurs near the trap center.