Metagenomics is a powerful technique for studying complex microbial communities. The key computational step in this method is clustering genomic sequences from mixed samples into potential microbial genomes, but accurately classifying sequences from complex metagenomes remains challenging. Some tools depend on k-mer frequency and coverage, but such methods struggle to distinguish between similar genomes. Methods that address the similar genomes problem, like ones that rely on single-copy marker genes, in turn struggle with complex datasets. The newly developed MetaDecoder balances these challenges by using both types of methods broken into two steps. First, MetaDecoder simplifies the dataset by generating preliminary groups of sequences with the Dirichlet Process Gaussian Mixture Model (DPGMM). Then, these preliminary clusters are clustered further with a k-mer frequency probabilistic model and a modified Gaussian Mixture Model of single-copy marker gene coverage. When tested on both simulated and real-world datasets, MetaDecoder generated more complete clusters with lower contamination than other tools. The run time and memory cost of MetaDecoder on a CPU-based station were comparable to those of other programs, but MetaDecoder can be greatly boosted by a GPU to surpass other programs in computational efficiency. Overall, MetaDecoder represents a promising new approach to metagenomic clustering.