Owing to the requirement of ever-increasing machining accuracy in tool machinery, the research on how to optimally design a reliable high-rigidity computer-numerical-controlled (CNC) machine tool is increasing in importance. Conventionally, machine designers carried out design optimization by attempting to maximize only the static stiffness. Nowadays, for high-precision machining, a good machine tool should have high rigidity not only under static stimuli but also under dynamic stimuli. The dynamic rigidity of the machine structure is thus receiving increasing attention. In this study, we propose an integral-stiffness-based optimization methodology for designing the optimal structure of a CNC horizontal machining center (HMC). The proposed novel optimization methodology is mainly based on Taguchi’s experimental method, the finite element method (FEM), and gray relational analysis (GRA). In addition, some specifically designed experiments on machine stiffness are performed using displacement sensors to verify the calculation results. The optimization parameters consist of the static stiffness, the first natural frequency, and the dynamic stiffness. Through the use of our proposed methodology, the optimal structural dimensions of the target HMC that give high integral rigidity can be determined. Moreover, the proposed optimization methodology provides a good guide for machine designers to design the high-rigidity structure of a CNC machine tool efficiently and accurately.