Estimates of non-microbial diversity on Earth range from 2 million to over 50 million species, with great uncertainties in numbers of insects, fungi, nematodes, and deep-sea organisms. We summarize estimates for major taxa, the methods used to obtain them, and prospects for further discoveries. Major challenges include frequent synonymy, the difficulty of discriminating certain species by morphology alone, and the fact that many undiscovered species are small, difficult to find, or have small geographic ranges. Cryptic species could be numerous in some taxa. Novel techniques, such as DNA barcoding, new databases, and crowd-sourcing, could greatly accelerate the rate of species discovery. Such advances are timely. Most missing species probably live in biodiversity hotspots, where habitat destruction is rife, and so current estimates of extinction rates from known species are too low.