This paper deals with the redesign of a machine tool substructure which reinforces the working table of a gantry type milling machine. The original design of the reinforcing structure is a grillage structure to strengthen the working table. In order to improve the design, the cutting edge technology of topology optimization is employed to redesign the reinforcing structure. The result obtained by topology optimization shows that the redesigned topology of the reinforced structure is totally different from that of the original design. With the same material used, the stiffness and the natural frequencies of the working table are much higher than the original design. Even with a less amount of material use, the stiffness and the natural frequencies are still improved significantly.