Evolutionary structural optimization (ESO) method is based on a simple idea that the optimal structure can be produced by gradually removing the ineffectively used material from the design domain. ESO seems to have some attractive features in engineering aspects: simple and fast. In this paper, ESO is applied to optimize shaft shape for the rotating machinery by introducing variable size of finite elements in optimization procedure. The goal of this optimization is to reduce total shaft weight and resonance magnification factor (Q factor), and to yield the critical speeds as far from the operating speed as possible. The constraints include restrictions on critical speed, unbalance response and bending stresses. Sensitivity analysis of the system parameters is also investigated. The results show that new ESO method can be efficiently used to optimize the shape of rotor shaft system with frequency and dynamic constraints.