Recent phylogenomic studies have established a robust backbone relationship for the seven subfamilies of jumping spiders (Salticidae), and identified an enigmatic clade within the subtribe Spartaeina, which significantly contributes to the diversity of the subfamily Spartaeinae. However, the classification of this enigmatic lineage remained unresolved due to the availability of only one male specimen at that time. In this study, we extensively examined additional materials and obtained ultra-conserved element (UCE) data for more putative species of this lineage. The UCE phylogenetic results provided a comprehensive and strongly supported framework for the subtribe Spartaeina, and confirmed that the enigmatic clade is a distinct lineage, separate from genera with similar morphological traits. Coupled with morphological evidence, we describe a new genus, Protaeus gen. nov., and three new species: Protaeus nyarlathotep sp. nov., P. dracosquamus sp. nov., and P. gulliwingus sp. nov. We also revise the classification of three previously misplaced species into this new genus: P. jianfeng (Song & Zhu, 1998) comb. nov. (transferred from Portia), P. forcipiformis (Yang, Liu, Liu & Peng, 2017) comb. nov. (transferred from Spartaeus) and P. shiwandashan (Wang, Mi, Li & Xu, 2024) comb. nov. (transferred from Mintonia). Additionally, we redescribe the male of P. jianfeng and provide a description of the female for the first time. This study enhances our understanding of evolutionary relationships within Spartaeina and underscores the importance of further exploration within this diverse group.