Amoebae that make fruiting bodies consisting of a stalk and spores and classified as closely related to the myxogastrids have classically been placed in the taxon Eumycetozoa. Traditionally, there are three groups comprising Eumycetozoa: myxogastrids, dictyostelids, and the so-called protostelids. Dictyostelids and myxogastrids both make multicellular fruiting bodies that may contain hundreds of spores. Protostelids are those amoebae that make simple fruiting bodies consisting of a stalk and one or a few spores. Protostelid-like organisms have been suggested as the progenitors of the myxogastrids and dictyostelids, and they have been used to formulate hypotheses on the evolution of fruiting within the group. Molecular phylogenies have been published for both myxogastrids and dictyostelids, but little molecular phylogenetic work has been done on the protostelids. Here we provide phylogenetic trees based on the small subunit ribosomal RNA gene (SSU) that include 21 protostelids along with publicly available sequences from a wide variety of amoebae and other eukaryotes. SSU trees recover seven well supported clades that contain protostelids but do not appear to be specifically related to one another and are often interspersed among established groups of amoebae that have never been reported to fruit. In fact, we show that at least two taxa unambiguously belong to amoebozoan lineages where fruiting has never been reported. These analyses indicate that we can reject a monophyletic Eumycetozoa, s.l. For this reason, we will hereafter refer to those slime molds with simple fruiting as protosteloid amoebae and/or protosteloid slime molds, not as protostelids. These results add to our understanding of amoebozoan biodiversity, and demonstrate that the paradigms for understanding both nonfruiting and sporulating amoebae must be integrated. Finally, we suggest strategies for future research on protosteloid amoebae and nonfruiting amoebae, and discuss the impact of this work for taxonomists and phylogenomicists.