The Pinnotheridae represents a diverse group of very small crabs associated with other invertebrates. Here we show that, among the brachyurans, pinnotherids display the greatest diversity in numbers of gills and gill grooming appendages, with a continuous spectrum ranging from eight to three gills per branchial chamber, on as many as five to as few as two gill bearing appendages. There is no linear relationship between the reduction of gill numbers and size of the crabs. The reduction of gills took place in both anterior and posterior thoracic regions. Also, unlike other Brachyura, some pinnotherids lack a gill grooming appendage on maxilliped 2. These taxa are characterized by four or fewer gills per branchial chamber. In the interest of clarifying the systematic position of species and genera within the Pinnotheridae, 13 adult characters related to gill formulas, morphology of grooming appendages and setae, and hosts were used with 13 larval characters to determine sister group relationships among 34 taxa. The higher Brachyura served as the outgroup in this phylogenetic analysis. It generated multiple trees from which strict consensus and 50% majority-rule consensus trees were computed. All trees identified the genusPinnothereliaas the most basal taxon, followed byAsthenognathusand the remaining pinnotherids. Members of the Pinnotherinae represent the most derived taxa among pinnotherids. This subfamily formed a separate clade, excluding taxa of the Pinnothereliinae and Asthenognathinae, with the exception ofPinnixaandOpisthopus, respectively. Basal to the Pinnotherinae,XenophthalmusandAnomalifronsformed sister taxa. The cladograms indicate progressive loss of gills, starting with the podobranch on maxilliped 3, followed by the podobranch on maxilliped 2 and pleurobranchs associated with pereiopods 2 and 3. Finally the epipodite of maxilliped 2 was lost.