Structural rigidity is a crucial factor that determines machining accuracy for computer-numerical-controlled (CNC) machines. Therefore, how to design a highly rigid CNC machine tool has been the focus of attention. In response to the rapid changes in various machine tools attributable to market needs, it is necessary to find an efficient way to examine and optimally design their structures. In this study, we propose an optimization methodology based on the finite element method (FEM) and sensor-based measurement to efficiently investigate and obtain an optimal structure with high rigidity of the selected target CNC movable-cross-beam double-column machining center (MDMC). The proposed methodology is mainly composed of the prototype design of a target machine, theoretical investigations via FEM, static as well as dynamic stiffness analysis, experimental measurements based on sensors, investigations on crucial parameters that mostly affect the whole structural strength, and the design of an optimum structure via synthesis and comparison. We found that a reduction as large as 1000 mm in the Z travel of a spindle head causes decreases as large as 69.37% in minimum static stiffness and 37.93% in minimum dynamic stiffness. It is suggested that, for optimally designing our target MDMC, the Z-travel length of the spindle head should be reduced to half the original size. This proposed methodology is a rapid, effective, and economical way to optimally design or modify the structure of a MDMC. It can also be used as an optimization guide of the structural design for other types of CNC machine tool.