In turning hardened steel, polycrystalline cubic boron nitride (cBN) compacts are widely used, due to their higher hardness and higher thermal conductivity. However, in milling hardened steel, fracture of cBN cutting tools readily occurs because they have poor fracture toughness. Therefore, coated cemented carbide tools, which have good fracture toughness and wear resistance, are generally widely used. In this study, hardened steel (ASTM D2, JIS SKD11, 60HRC) was milled with three physical vapor deposition (PVD)-coated cemented carbide end mill cutters in order to determine effective tool materials for cutting hardened steel at high cutting speeds. The coating films used were (Ti,W)N/(Ti,W,Si)N and (Ti,W)N/(Ti,W,Si,Al)N coating films. (Ti,W,Si,Al)N is a new type of coating film. The inner layer of the (Ti,W)N/(Ti,W,Si)N and (Ti,W)N/(Ti,W,Si,Al)N coating system is (Ti,W)N coating film, and the outer layer is (Ti,W,Si)N and (Ti,W,Si,Al)N coating films, respectively. Furthermore, commercial (Ti,Al)N-based coating film was also used. The following results were obtained: (1) In milling hardened steel at a cutting speed of 3.33 m/s, the tool wear width of the (Ti,W)N/(Ti,W,Si,Al)N-coated tool was smaller than that of the (Ti,W)N/(Ti,W,Si)N-coated tool. And, compared with the commercial (Ti,Al)N, the tool wear width of the (Ti,W)N/(Ti,W,Si,Al)N-coated tool was smaller than that of the (Ti,Al)N-coated tool. (2) The tool wear of the (Ti,W)N/(Ti,W,Si,Al)N-coated tool increased with an increase in cutting speed. (3) The (Ti,W)N/(Ti,W,Si,Al)N-coated cemented carbide was an effective tool material for high-speed cutting below a cutting speed of 3.33 m/s.