Partitioning technology is used widely in industry, such as prototype production, stock generation, and mold design. To reduce human factors in partitioning results, increase the precision and efficiency of computation, and ensure the rationality of partitioning scheme, a feature-based partitioning algorithm for complex model is proposed. It consists of four steps: ( 1) graph-based algorithm is used to extract the concave or undercut features, which may need partitioning; ( 2) an improved VMap visibility analysis algorithm is used to judge whether the model or features could be machined using three-axis computer numerical controlled (CNC) machine or approached directly, if not; ( 3) all candidate-partitioning faces are selected according to certain constraints; ( 4) and the optimal partitioning scheme is obtained by multi-objective genetic algorithm considering partitioning pieces number, material utilization, numbers of machining features, and partitioning area as its objective functions. After the partitioning, each component has simpler geometric form and can be machined using three-axis CNC machine economically. Case studies demonstrate the validity of the proposed method.