Published ages of >50 ka for occupation at Madjedbebe (Malakunanja II) in Australia's north have kept the site prominent in discussions about the colonisation of Sahul. The site also contains one of the largest stone artefact assemblages in Sahul for this early period. However, the stone artefacts and other important archaeological components of the site have never been described in detail, leading to persistent doubts about its stratigraphic integrity. We report on our analysis of the stone artefacts and faunal and other materials recovered during the 1989 excavations, as well as the stratigraphy and depositional history recorded by the original excavators. We demonstrate that the technology and raw materials of the early assemblage are distinctive from those in the overlying layers. Silcrete and quartzite artefacts are common in the early assemblage, which also includes edge-ground axe fragments and ground haematite. The lower flaked stone assemblage is distinctive, comprising a mix of long convergent flakes, some radial flakes with faceted platforms, and many small thin silcrete flakes that we interpret as thinning flakes. Residue and use-wear analysis indicate occasional grinding of haematite and woodworking, as well as frequent abrading of platform edges on thinning flakes. We conclude that previous claims of extensive displacement of artefacts and post-depositional disturbance may have been overstated. The stone artefacts and stratigraphic details support previous claims for human occupation 50–60 ka and show that human occupation during this time differed from later periods. We discuss the implications of these new data for understanding the first human colonisation of Sahul.