The presence and distribution of two species of Notanisus Walker (Hymenoptera: Pteromalidae) in North America is reported. Notanisus sexramosus (Erdős), originally described from Hungary and previously reported from Maryland, USA, is recorded also from Massachusetts and Pennsylvania based on a male and macropterous and brachypterous females. Males of Notanisus are shown to have two types of flagellar structure, ramose and pedicellate, and diagnostic features are given for the previously unknown males of N. clavatus Bouček to differentiate these from those of N. sexramosus and N. versicolor Walker. Five other species are newly described, Notanisus kansensis n. sp. based on a female from Nebraska, USA, and four species from Sub-Saharan Africa and the Arabian Peninsula--Notanisus brevipetiolus n. sp. based on two females from Uganda and Zambia, Notanisus longipetiolus n. sp. based on a female from Zimbabwe and a female and two males from Mozambique, Notanisus vanharteni n. sp. based on a female and several males from United Arab Emirates, and Notanisus yemenensis n. sp. based on a female and male from Yemen. The latter five species are included with the Palaearctic species N. oulmesiensis (Delucchi) and N. gracilis (Yang) in the oulmesiensis species group, defined by the presence of reduced stigmal and postmarginal veins in both sexes. The seven oulmesiensis-group species are differentiated in a key and all treated species are illustrated through macrophotography. Monophyly and relationships of Notanisus within Cleonymini are discussed, including features that indicate it could be paraphyletic relative to Callocleonymus Masi.