Most studies of brachiopod evolution have been based on their extensive fossil record, but molecular techniques, due to their independence from the rock record, can offer new insights into the evolution of a clade. Previous molecular phylogenetic hypotheses of brachiopod interrelationships place phoronids within the brachiopods as the sister group to the inarticulates, whereas morphological considerations suggest that Brachiopoda is a monophyletic group. Here, these hypotheses were tested with a molecular phylogenetic analysis of seven nuclear housekeeping genes combined with three ribosomal genes. The combined analysis finds brachiopods to be monophyletic, but with relatively weak support, and the craniid as the sister taxon of all other brachiopods. Phylogenetic-signal dissection suggests that the weak support is caused by the instability of the craniid, which is attracted to the phoronids. Analysis of slowly evolving sites results in a robustly supported monophyletic Brachiopoda and Inarticulata (Linguliformea+Craniiformea), which is regarded as the most likely topology for brachiopod interrelationships. The monophyly of Brachiopoda was further tested with microRNA-based phylogenetics, which are small, noncoding RNA genes whose presence and absence can be used to infer phylogenetic relationships. Two novel microRNAs were characterized supporting the monophyly of brachiopods. Congruence of the traditional molecular phylogenetic analysis, microRNAs, and morphological cladograms suggest that Brachiopoda is monophyletic with Phoronida as its likely sister group. Molecular clock analysis suggests that extant phoronids have a Paleozoic divergence despite their conservative morphology, and that the early brachiopod fossil record is robust, and is not affected by taphonomic factors relating to the late-Precambrian/early-Cambrian phosphogenic event.