We propose a phylogenetic hypothesis of relationships within Callandrena, a North American subgenus of the bee genus Andrena, based on both mitochondrial and nuclear DNA sequences. Our data included 695 aligned base pairs comprising parts of the mitochondrial genes cytochrome oxidase subunits I and II and the intervening tRNA-leucine and 767 aligned base pairs of the F2 copy of the nuclear gene elongation factor-1alpha. We also suggest a preliminary hypothesis of relationships of the North American subgenera in the genus. Our analyses included 54 species of Callandrena, 42 species of Andrena representing 24 additional subgenera, and 11 outgroup species in the family Andrenidae. Parsimony analyses of each marker separately suggested that Callandrena was polyphyletic, with a combined analysis suggesting that there were at least two phylogenetically independent clades of bees with similar morphological features. Maximum likelihood and Bayesian analyses supported this conclusion, as did the non-parametric bootstrapping SOWH test. Convergence in morphological characters was likely due to their common use of members of Asteraceae as pollen hosts.