A new arthropod, Kootenichela deppi n. gen. n. sp., is described from the Stanley Glacier exposure of the middle Cambrian (Series 3, Stage 5) Stephen Formation in Kootenay National Park (British Columbia, Canada). This taxon possesses a number of primitive arthropod features such as an elongate, homonomous trunk (consisting of at least 29 segments), poorly sclerotised trunk appendages, and large pedunculate eyes associated with an anterior (ocular) sclerite. The cephalon encompasses a possible antenna-like appendage and enlarged raptorial appendages with a bipartite peduncle and three spinose distal podomeres, indicative of megacheiran (“great-appendage” arthropod) affinities. The relationships of megacheirans are controversial, with them generally considered as either stem-euarthropods or a paraphyletic stem-lineage of chelicerates. An extensive cladistic analysis resolved Kootenichela as sister-taxon to the enigmatic Worthenella cambria from the middle Cambrian (Series 3, Stage 5), Burgess Shale Formation in Yoho National Park (British Columbia), which is herein reinterpreted as a megacheiran arthropod. Based on their sister-group relationship, both taxa were placed in the new family Kootenichelidae, to which Pseudoiulia from the Chengjiang biota is also tentatively assigned. All of these taxa possess an elongate, multi-segmented body and subtriangular exopods. This family occupies a basal position within a paraphyletic Megacheira, the immediate outgroup of Euarthropoda (crown-group arthropods). The resultant topology indicates that analyses that have resolved megacheirans as stem-chelicerates have done so because they have rooted on inappropriate taxa, e.g., trilobitomorphs and marrellomorphs.