A new species of the genus Diomedenema, a spiruromorph nematode, collected from the lung of Spheniscus magellanicus (Sphenisciformes) found on the southern coast of the state of Rio Grande do Sul, Brazil, is described. The new species is differentiated from the only previously described species of the genus, D. diomedeae Johston & Mawson, 1952, by males possessing a set of caudal papillae with three pairs of precloacal, two pairs of adcloacal and one pair of postcloacal papillae; precloacal papillae with the papillae of the first two pairs being closer to each other than those of the third pair; a longer and pointed tail in males; and females with the vulva at mid-body. This is the first report of a nematode infecting the lung of a sphenisciforme host.