In five-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 cutter posture change from one cutter contact point to the next needs to be minimized. This paper presents a new method for generating five-axis tool-paths with smooth tool motion and high efficiency based on the accessibility map (A-map) of the cutter at a point on the part surface. The cutter’s A-map at a point refers to its posture range in terms of the two rotational angles, within which the cutter does not have any interference with the part and the surrounding objects. By using the A-map at a point, the posture change rates along the possible cutting directions (called the smoothness map or S-map) at the point are estimated. Based on the A-maps and S-maps of all the sampled points of the part surface, the initial tool-path with the smoothest posture change is generated first. Subsequently, the adjacent tool-paths are generated one at a time by considering both path smoothness and machining efficiency. Compared with traditional tool-path generation methods, e.g., iso-planar, the proposed method can generate tool-paths with smaller posture change rate and yet shorter overall path length. The developed techniques can be used to automate five-axis tool-path generation, in particular for high speed machining (finish cut).