Ein grosser Teil des Nationalparks ist im Besitz von Aborigines (Gagudju Association), die seit mindestens 60'000 Jahren (neueren Forschungen zufolge möglicherweise sogar seit 100 000 Jahren) hier legen und deren Mythologie aufs engste mit diesem Territorium verbunden ist.

Die in Kakadu vorhanden Kunststätten der Aborigines sind weltberühmt und die zahlreichen Kunstwerke an Klippen, Felswänden und in grossen natürlichen Felsbehausungen zeugen von der Geschichte, Kultur und Mythologie der Aborigines und darüber hinaus vom Kontakt zu den Makasaren, die aus Indonesien kamen, um hier zu fischen, Seegurken zu sammeln und nach Perlen zu tauchen. Die Ockermalereien von Kakadu enthalten zudem Darstellungen der Niederländer und später auch der Briten mit ihren Schiffen, Aexten und Feuerwaffen.

East Alligator, South Alligator und West Alligator River erhielten ihre Namen 1818 durch den Landvermesser Phillip Parker King, der die zahlreichen an den Flussufern lebenden Krokodile fälschlicherweise für Alligatoren hielt. Der deutsche Entdeckungsreisende Ludwig Leichhardt, der 1845 eine 15monatige Landexpedition von Moreton Bay (QLD) startete, stand als erster Europäer auf dem Steilabbruch von Arnhem Land.

Im Jahr 1979 erfolgte die Ernennung zum Nationalpark, 1981 die Einstufung als World Heritage. Der mehrfach erweiterte Park umfasst heute eine Fläche von 19'800 Quadratkilometern.