It is part of the lands traditionally inhabited by the Mirarr, an Aboriginal Australian clan of the Gaagudju people, of the Gunwinyguan language group.

[1] Although it is surrounded by the World Heritage Listed Kakadu National Park, Madjedbebe itself is located within the Jabiluka Mineral Leasehold.

In 1973 archaeologist Johan Kamminga carried out a small-scale test pit excavation to a depth of nearly 2.5 m below surface, which provided the first evidence that the site contained a Pleistocene-aged occupation history.

[6] Although it is best known as Australia's oldest archaeological site, Madjedbebe also includes an extensive assemblage of rock art motifs on the walls.

In 2012 a research team from the Australian National University systematically documented the rock art at the site, under the auspices of the Mirarr Gunwarddebim Project.

As many of the images are faded, and many overlap, this is the minimum number of motifs the site that can be seen today; no doubt in the past there were many hundreds more present that no longer survive.

The latter include firearms,[31] European people (wearing clothing, hats and standing in a characteristic 'hands on hip' manner), pipes, knives and ships.

[22] These are a tantalising suggestion that even at this early time people were engaging in some form of artistic pursuit, whether that was painting motifs on the walls of the shelter, or decorating objects or themselves with the ground ochre.