Army ants (Hymenoptera: Formicidae: Dorylinae) are keystone predators throughout most of the tropical and subtropical regions of the world. One of the most wide-ranging and ecologically important army ant genera is Labidus, which has a broad dietary niche and often high local abundance in the Neotropical region. Labidus taxonomy at the species level is in need of revision. Currently, seven valid species are recognized based on the morphology of workers and/or males, but little information on cryptic species within or phylogenetic relationships among them is available. Here, we attempt to define species boundaries within the genus by reconstructing its phylogeny using DNA "barcodes" (a segment of the mitochondrial COI gene) from 2,513 specimens, ultra-conserved element (UCE) data from six Labidus specimens plus two outgroup taxa, and COI barcodes extracted from UCE contigs. Phylogenies were reconstructed with Maximum Likelihood analyses, and based on a reconstructed UCE topology, a constraint tree topology was obtained with 74 specimens. Our analyses revealed at least seven COI clusters, with three of the species mainly characterized by the worker caste corresponding to multiple putative cryptic species. Our phylogeny also allowed us to associate two species known only from males with their respective workers. With the addition of more UCE data, morphological data, and species delimitation analyses, a reliable updated taxonomy of Labidus will emerge.