Following the arrival of non-native species into suitable environments, interactions with native biota can influence non-native species proliferation and spread. The European shore crab, Carcinus maenas, is a global invader for which top-down control by predators has been implicated in limiting range expansion in its North American range. Little is known, however, about predators of this non-native species within its Australian distribution. We conducted quarterly trapping over 2 years in ten Australian estuaries to assess relationships between the abundance of C. maenas and native predators. Feeding assays between C. maenas and putative predators, identified from negative associations in occurrence, assessed the ability of putative predators to recognise C. maenas as prey. Six taxa were negatively correlated with C. maenas’ abundance and capable of eating the non-native crab. These were the blue swimmer crab (Portunus pelagicus), octopods (Octopus spp.), leatherjackets (Monocanthidae), yellowfin bream (Acanthopagrus australis), toadfish (Tetraodontidae) and the eastern fiddler ray (Trygonorrhina fasciata). Octopus spp. were rare in and blue swimmer crabs absent from mangroves; the habitat in which C. maenas was most abundant. A tethering experiment confirmed that Octopus spp. eat C. maenas in the field, with greater rates of mortality of the crab close to than away from the Octopus spp. lairs. Overall, our study indicates that a diverse assemblage of predators may prey upon C. maenas in southeastern Australia. Further studies assessing relative rates of predation by these predators on C. maenas are needed to assess whether they are exerting significant top-down control.