Middle Ordovician brachiopod faunas from the Amadeus Basin, central Australia are poorly known. The Darriwilian Stairway Sandstone was sampled stratigraphically for macrofossils in order to provide new information on marine benthic diversity in this clastic-dominated, shallow-water palaeoenvironment along the margin of northeastern Gondwana. The brachiopods from the Stairway Sandstone are of low diversity and represent ca 9% of the entire shelly fauna. Five brachiopod taxa are described from the Stairway Sandstone; all are endemic to the Amadeus Basin at species level. Two new species, Amadeuphyla joanae gen. et sp. nov. and Paralenorthis luritjaorum sp. nov., are described. Unweighted cladistic analysis based on 20 characters places the new genus Amadeuphyla within the Taffinae.