Headstock is a key component of gear milling machine. The dynamic functional performance of the headstock is usually influenced by uncertainties of both geometric and non-geometric design parameters. A new mathematical model to represent relationships among first frequency and design parameters of the headstock were derived with Rayleigh method. Then, a larger-the-better and smaller-the-better robust analysis and optimization model was developed. The sensitivity analysis results show that height of the headstock makes a great impact on the first frequency. Through robust optimizations, the first frequency is scaled up by 3.35 percent while minimizing the variance of the first frequency.