A new species of stalked puffball, Tulostoma rufescens, was observed and collected from subtropical scrub vegetation within the Sonoran Sky Islands, Mexico, and was characterized morphologically and molecularly. The new fungus is characterized by small to medium sized spore-sacs, a thinly membranous exoperidium persisting in patches in the pinkish endoperidium, a tortuous stem with a basal bulb strongly intermixed with sand and debris, subhyaline capillitia with swollen and pigmented septa, and strongly echinulate basidiospores with spines that occasionally coalesce to form a subreticulum. Maximum likelihood and neighbor-joining phylogenetic analyses of full ITS1-5.8S-ITS2 and D1-D2 LSU DNA regions placed our collection within the monophyletic genus Tulostoma but separate from all of the available sequenced species.