This paper presents a novel optimal design framework for a multi-stage interceptor considering the engagement boundary. The framework utilizes the Cross-Entropy Method(CEM) to handle the complex design procedure, considering system and subsystem requirements. Optimal stage designs are applied to achieve effective mass distribution at each stage. Remarkably, the proposed population-based derivative-free design method exhibits excellent convergence performance even with intricate design components, involving aerodynamic calculations using Missile DATCOM and nonlinear simulations for evaluation. The interceptor model in the nonlinear simulation accompanies coasting phases and corresponding guidance strategy, and thus the framework can consider the operational characteristics of a multi-stage interceptor during the optimal design phase. A case study demonstrates that the proposed framework can effectively satisfy the system requirements and subsystem constraints.