In 5-axis high speed milling, one of the key requirements to ensure the quality of the machined surface is that the tool-path must be smooth, i.e., the posture change from one point to the next must be minimized. In this paper, a new method for generating optimal 5-axis tool-paths with smooth cutter motion and high efficiency is presented. The basis of this optimization method is a new concept called cutter smoothness map (S-map, i.e., posture change rates along possible cutting directions) at a point on the part surface. With the S-map at any given point on the part surface, the initial tool-path with the smoothest posture change can be generated. Subsequently, the adjacent tool-paths are generated one at a time by considering both machining efficiency and path smoothness. Compared with traditional tool-path patterns, e.g., iso-planar, the generated tool-paths are smoother in terms of posture changes along the tool-path, thus better surface finish is expected. An example is presented to demonstrate the effectiveness and validity of the proposed method.