High-throughput sequencing is a revolutionary technology for the analysis of metagenomic samples. However, querying large volumes of reads against comprehensive DNA/RNA databases in a sensitive manner can be compute-intensive. Here, we present taxMaps, a highly efficient, sensitive and fully scalable taxonomic classification tool. Using a combination of simulated and real metagenomics datasets, we demonstrate that taxMaps is more sensitive and more precise than widely used taxonomic classifiers, being capable of delivering classification accuracy comparable to that of BLASTn, but at up to 3 orders of magnitude less computational cost.