A coated cutting tool comprising a substrate and a coating layer formed on a surface of the substrate, the coating layer including at least one predetermined layer, wherein: the predetermined layer is a layer containing a compound having a composition represented by a formula below: (AlxTiyM1-x-y)N [wherein M denotes an element of at least one kind selected from the group consisting of Zr, Hf, V, Nb, Ta, Cr, Mo, W and Si, x denotes an atomic ratio of the Al element based on a total of the Al element, the Ti element and a metal element denoted by M, y denotes an atomic ratio of the Ti element based on a total of the Al element, the Ti element and the metal element denoted by M, x satisfies 0.60≤x≤0.85, y satisfies 0≤y≤0.40, and x+y satisfies 0.60≤x+y≤1.00]; an average thickness of the predetermined layer is from 1.4 μm or more to 15 μm or less; and the predetermined layer has an upper region and a lower region which satisfy conditions (1), (2) and (3) below: condition (1): the upper region has an average thickness of from 0.5 μm or more to 2.5 μm or less ranging from an interface which is close to a surface of the coated cutting tool toward the substrate, the average thickness being less than an average thickness of the predetermined layer, and the lower region has an average thickness of from 0.5 μm or more to 2.5 μm or less ranging from an interface which is close to the substrate toward the surface of the coated cutting tool, the average thickness being less than the average thickness of the predetermined layer; (2) an atomic ratio of the Al element contained in the upper region is higher, by from 3 atom % or higher to 10 atom % or lower, than an atomic ratio of the Al element contained in the lower region; and (3) an average particle size in the upper region is greater than an average particle size in the lower region.