King crabs (Family Lithodidae) are among the world's largest arthropods, having a crab-like morphology and a strongly calcified exoskeleton. The hermit crabs, by contrast, have depended on gastropod shells for protection for over 150 million years. Shell-living has constrained the morphological evolution of hermit crabs by requiring a decalcified asymmetrical abdomen capable of coiling into gastropod shells and by preventing crabs from growing past the size of the largest available shells. Whereas reduction in shell-living and acquisition of a crab-like morphology (carcinization) has taken place independently in several hermit crab lineages, and most dramatically in king crabs, the rate at which this process has occurred was entirely unknown. We present molecular evidence that king crabs are not only descended from hermit crabs, but are nested within the hermit crab genus Pagurus. We estimate that loss of the shell-living habit and the complete carcinization of king crabs has taken between 13 and 25 million years.