The previously monotypic genus, Paramyiolia Shiraki, is redefined based on the type species, P. takeuchii Shiraki, plus three species formerly known as Anomoia cornuta Ito, Myoleja rhino Steyskal, and Myoleja nigricornis (Doane). A key to the species, descriptions and illustrations are presented, and their phylogenetic relationships are analyzed. Paramyiolia is here placed in the Chetostoma group (Trypetinae, Trypetini), which includes four additional genera: Anomoia Walker, Chetostoma Rondani, Myoleja Rondani (s. str.), and Montiludia Ito. Hypothesized synapomorphies for the Chetostoma group are also discussed. In addition, the taxonomic status of New World tephritids formerly placed in Myoleja is clarified, resulting in the following nomenclatural changes: transfer of Myoleja limata (Coquillett), Acidia fallax Johnson, and Hamouchaeta ogloblini Blanchard to Parastenopa Hendel and synonymization of Hamouchaeta Blanchard with Parastenopa.