In this two-part paper, a new methodology for feature recognition (FR) and machining planning is described. Most of the earlier FR work was aimed at facilitation of machining planning by extraction of simple shaped features. Our method deviates from earlier strategies, attempting to recognize relatively complex shaped features that are not only machinable, but also allow smart machining planning to reduce total machining time. This new approach has two advantages: allowing complex-shaped features leads to computational advantages, simplifying the recognition; also, the ability to generate near-optimal machining plans for complex pockets results in reduced total machining time for parts. The first part of this paper concentrates on the details of the machining feature extraction procedures. The algorithms are presented, and examples provided. The recognition system has been tested successfully for over 70 parts from the NIST part repository, including most benchmark parts from research and industry. The second part of the paper will describe a multiple-tool milling planning technique. Results will be presented to prove the viability of this system.