Morphology-based phylogenetic analyses support the monophyly of the Scalidophora (Kinorhyncha, Loricifera, Priapulida) and Nematoida (Nematoda, Nematomorpha), together constituting the monophyletic Cycloneuralia that is the sister group of the Panarthropoda. Kinorhynchs are unique among living cycloneuralians in having a segmented body with repeated cuticular plates, longitudinal muscles, dorsoventral muscles, and ganglia. Molecular clock estimates suggest that kinorhynchs may have diverged in the Ediacaran Period. Remarkably, no kinorhynch fossils have been discovered, in sharp contrast to priapulids and loriciferans that are represented by numerous Cambrian fossils. Here we describe several early Cambrian (~535 million years old) kinorhynch-like fossils, including the new species Eokinorhynchus rarus and two unnamed but related forms. E. rarus has characteristic scalidophoran features, including an introvert with pentaradially arranged hollow scalids. Its trunk bears at least 20 annuli each consisting of numerous small rectangular plates, and is armored with five pairs of large and bilaterally placed sclerites. Its trunk annuli are reminiscent of the epidermis segments of kinorhynchs. A phylogenetic analysis resolves E. rarus as a stem-group kinorhynch. Thus, the fossil record confirms that all three scalidophoran phyla diverged no later than the Cambrian Period.