A new record of the encyrtid Neastymachus luteus Nikol'skaya (1952) (Chalcidoidea, Encyrtidae, Encyrtinae), far from its known distribution area, is presented. Several individuals of this parasitic Hymenoptera were reared from Aclerda berlesii Buffa (1897) females on the large perennial grass Arundo donax Linnaeus (1753) in the province of Alicante, Spain. This is the first occurrence of this chalcidoid species for Western Europe; previously it was quoted from the West Palearctic (Algeria). The only insect host known until now for this parasitoid was Nipponaclerda turanica Borchsenius (1950) (Aclerdidae) on Phragmites vulgaris. The female of N. luteus is fully illustrated and described for the first time.