Morphological data traditionally group Tardigrada (water bears), Onychophora (velvet worms), and Arthropoda (e.g., spiders, insects, and their allies) into a monophyletic group of invertebrates with walking appendages known as the Panarthropoda. However, molecular data generally do not support the inclusion of tardigrades within the Panarthropoda, but instead place them closer to Nematoda (roundworms). Here we present results from the analyses of two independent genomic datasets, expressed sequence tags (ESTs) and microRNAs (miRNAs), which congruently resolve the phylogenetic relationships of Tardigrada. Our EST analyses, based on 49,023 amino acid sites from 255 proteins, significantly support a monophyletic Panarthropoda including Tardigrada and suggest a sister group relationship between Arthropoda and Onychophora. Using careful experimental manipulations--comparisons of model fit, signal dissection, and taxonomic pruning--we show that support for a Tardigrada + Nematoda group derives from the phylogenetic artifact of long-branch attraction. Our small RNA libraries fully support our EST results; no miRNAs were found to link Tardigrada and Nematoda, whereas all panarthropods were found to share one unique miRNA (miR-276). In addition, Onychophora and Arthropoda were found to share a second miRNA (miR-305). Our study confirms the monophyly of the legged ecdysozoans, shows that past support for a Tardigrada + Nematoda group was due to long-branch attraction, and suggests that the velvet worms are the sister group to the arthropods.