The present invention provides a composite material that is excellent in the bonding ability between a cemented carbide layer and a cermet layer is excellent and deformation after sintering can be suppressed and a coated cutting tool having a base containing the composite material. A composite material 10ii is obtained by laminating a cemented carbide layer 11 and a cermet layer 12 and has the cemented carbide layer 11 on the surface side. The boundary between both the layers 11 and 12 has a concave portion 23, and the maximum depth Dmax of the concave portion 23 is 50 μm or more and 500 μm or lower. When the thickness of the composite material is defined as h1 and the thickness of the cemented carbide layer 11 is defined as h2, h2/h1 is in the range of more than 0.02 and 0.4 or lower. By providing the concave portion 23 to the boundary, both the layers 11 and 12 are sufficiently bound and the bonding ability therebetween is excellent. Due to the fact the cemented carbide layer 11 satisfies the given thickness mentioned above, the composite material 10 is difficult to deform.