A new species of dioecious Solanum from the Australian “Dioicum Complex” of Solanum subgenus Leptostemonum is described. Solanum cowiei Martine sp. nov., is allied with other members of this problematic lineage, but differs in its slender leaves, limited armature and diminutive habit. The species was first segregated by botanists at the Northern Territory Herbarium as Solanum sp. Litchfield (I.D. Cowie 1428); and specimens representing this species have also been referred to by Symon as Solanum sp. Fitzmaurice River. Collections suggest that this is an endemic of the sub-arid tropical zone of the Northern Territory. SEM images support initial assumptions that the new species is cryptically dioecious via production of inaperturate pollen grains in morphologically hermaphrodite flowers.