Sex differences in executive speech tasks, favoring women, have been noted in behavioral studies and functional imaging studies. In the present study, the clustering and switching components of semantic and phonemic verbal fluency tests were examined in 40 healthy men and 40 healthy women. Possible sex differences in the influence of cognitive factors such as speed of information processing, word knowledge, and/or verbal long-term memory on these verbal fluency factors were also assessed. The results showed that women switched more often between categories in the phonemic fluency test, whereas men showed a trend toward a larger cluster size leading to a smaller total number of words generated. Additionally, higher performance on the Digit Symbol test was associated with better performance on the semantic and phonemic verbal fluency test in men, whereas in women, better memory performance was associated with better performance on these verbal fluency tests. Our data indicate that men and women are using different processing strategies for phonemic verbal fluency tests to optimize verbal fluency task performance. In the current study, women adopted a more successful strategy of balancing clustering and switching in the phonemic fluency task.