El nombre de la provincia es derivado de la frase maguindanao "kuta wato" que significa "fuerte de roca", refiriendo a la fortaleza de roca del sultan Muhammad Dipatuan Kudarat en la ciudad de Cotabato.