A coated cutting tool has a substrate and a coating layer. At least one layer of the coating layer is a coarse grain layer with an average layer thickness of 0.2 to 10 μm and an average grain diameter in excess of 200 nm measured at the direction parallel to the interface of the coating layer. A composition of the layer is represented by (AlaTibMc)X, wherein M represents at least one of Zr, Hf, V, Nb, Ta, Cr, Mo, W, Y, B and Si, X represents at least one of C, N and O, and a, b and c represents atomic ratios of Al, Ti and M relative to one another such that 0.30≦a≦0.65, 0.35≦0.70, 0≦c≦0.20 and a+b+c=1.