Conifer-feeding sawflies in the genus Neodiprion provide an excellent opportunity to investigate the origin and maintenance of barriers to reproduction, but obtaining a phylogenetic estimate for comparative studies of Neodiprion speciation has proved difficult. Specifically, nonmonophyly within and discordance between individual gene trees, both of which are common in groups that diverged recently and/or rapidly, make it impossible to infer a species tree using methods that are designed to estimate gene trees. Therefore, in this study, we estimate relationships between members of the lecontei species group using four approaches that are intended to estimate species, not gene, trees: (1) minimize deep coalescences (MDC), (2) shallowest divergences (SD), (3) Bayesian estimation of species trees (BEST), and (4) a novel approach that combines concatenation with monophyly constraints (CMC). Multiple populations are sampled for most species and all four methods incorporate this intraspecific variation into estimates of interspecific relationships. We investigate the sensitivity of each method to taxonomic sampling, and, for the BEST method, we assess the impact of prior choice on species-tree inference. We also compare species-tree estimates to one another and to a morphologically based hypothesis to identify clades that are supported by multiple analyses and lines of evidence. We find that both taxonomic sampling and method choice impact species-tree estimates and that, for these data, the BEST method is strongly influenced by Theta and branch-length priors. We also find that the CMC method is the least sensitive to taxonomic sampling. Finally, although interspecific genetic variation is low due to the recent divergence of the lecontei group, our results to date suggest that incomplete lineage sorting and interspecific gene flow are the main factors complicating species-tree inference in Neodiprion. Based on these analyses, we propose a phylogenetic hypothesis for the lecontei group. Finally, our results suggest that, even for very challenging groups like Neodiprion, an underlying species-tree signal can be extracted from multi-locus data as long as intraspecific variation is adequately sampled and methods that focus on the estimation of species trees are used.