We provided the first scientific record of Melanagromyza sojae (Zehntner, 1900), through molecular characterization of partial mtDNA COI gene, that confirms the occurrence of this pest in Paraguay. Previously reported in Brazil, an outbreak of larvae of M. sojae known as the soybean stem fly (SSF) that belongs to the family Agromyzidae, was also noted in soybean fields from the Canindeyú, Alto Paraná and Itapúa Departments in Paraguay. This pest is highly polyphagous, attacking various host plant species from the family Fabaceae, such as soybean and other beans. The implications of SSF detection in Paraguay are discussed in relation to the current soybean cultivation practices from this agriculturally important South American region, including Brazil.