Malongitubus kuangshanensis Hu, 2005 from the early Cambrian Chengjiang Lagerstatte of China is redescribed as a pterobranch and provides the best evidence to demonstrate that hemichordates were present as early as Cambrian Stage 3. Interpretation of this taxon as a hemichordate is based on the morphology of the branched colony and the presence of resistant inner threads consistent with the remains of an internal stolon system. The presence of fusellar rings in the colonial tubes cannot be unambiguously proven for Malongitubus, probably due to early decay and later diagenetic replacement of the thin organic material of the tubarium, although weak annulations are still discernible in parts of the tubes. The description of M. kuangshanensis is revised according to new observations of previously reported specimens and recently collected additional new material. Malongitubus appears similar in most features to Dalyia racemata Walcott, 1919 from the Cambrian Stage 5 Burgess Shale, but can be distinguished by the existence of disc-like thickenings at the bases of tubarium branching points in the latter species. Both species occur in rare mass-occurrence layers with preserved fragmentary individuals of different decay stages, with stolon remains preserved as the most durable structures. Benthic pterobranchs may have occurred in some early Cambrian shallow marine communities in dense accumulations and provided firm substrates and shelter for other benthic metazoans as secondary tierers.