Interest in understanding the extent of plastic and specifically microplastic pollution has increased on a global scale. However, we still know relatively little about how much plastic pollution has found its way into the deeper areas of the world’s oceans. The extent of microplastic pollution in deep-sea sediments remains poorly quantified, but this knowledge is imperative for predicting the distribution and potential impacts of global plastic pollution. To address this knowledge gap, we quantified microplastics in deep-sea sediments from the Great Australian Bight using an adapted density separation and dye fluorescence technique. We analyzed sediment cores from six locations (1–6 cores each, n = 16 total samples) ranging in depth from 1,655 to 3,062 m and offshore distances ranging from 288 to 356 km from the Australian coastline. Microplastic counts ranged from 0 to 13.6 fragments per g dry sediment (mean 1.26 ± 0.68; n = 51). We found substantially higher microplastic counts than recorded in other analyses of deep-sea sediments. Overall, the number of microplastic fragments in the sediment increased as surface plastic counts increased, and as the seafloor slope angle increased. However, microplastic counts were highly variable, with heterogeneity between sediment cores from the same location greater than the variation across sampling sites. Based on our empirical data, we conservatively estimate 14 million tonnes of microplastic reside on the ocean floor.