Microplastic pollutants occur in marine environments globally, however estimates of seafloor concentrations are rare. Here we apply a novel method to quantify size-graded (0.038–4.0 mm diam.) concentrations of plastics in marine sediments from 42 coastal and estuarine sites spanning pollution gradients across south-eastern Australia. Acid digestion/density separation revealed 9552 individual microplastics from 2.84 l of sediment across all samples; equating to a regional average of 3.4 microplastics·ml− 1 sediment. Microplastics occurred as filaments (84% of total) and particle forms (16% of total). Positive correlations between microplastic filaments and wave exposure, and microplastic particles with finer sediments, indicate hydrological/sediment-matrix properties are important for deposition/retention. Contrary to expectations, positive relationships were not evident between microplastics and other pollutants (heavy metals/sewage), nor were negative relationships with neighbouring reef biota detected. Rather, microplastics were ubiquitous across sampling sites. Positive associations with some faunal-elements (i.e. invertebrate species richness) nevertheless suggest high potential for microplastic ingestion.