Based on the analysis of the disadvantages of shoe last making with 3-axis shoe last NC machine, this paper presents a novel solution for last making with 5-axis shoe last NC machine, introduces the working principles, motions, components and implementation of 5-axis shoe last NC machine in detail. A key feature of the machine is that it can produce complete lasts in one working process, avoiding milling the toe and heel with final manual finishing operations. This paper proposes an algorithm of the tool path generation of the machine. By the grid data of the last surfaces and spiral interpolation, we can obtain the cutter contact points and cutter location points and then deduce the formula of solving each component motion in the machining. A model machine developed by the presented solution demonstrates the improved machining efficiency and high quality of shoe last.