The fauna of phytoseiid mites in the state of Mato Grosso do Sul, in midwestern Brazil, is poorly known. The tomato red spider mite, Tetranychus evansi Baker and Pritchard, is an important pest of Solanaceae in several countries, but it is usually found in low densities in Brazil. It has been hypothesized that this is due to the effect of natural enemies. The objective of this study was to identify phytoseiid mites from Mato Grosso do Sul associated with T. evansi, to identify promising biological control agents for T. evansi in Africa. A survey was conducted in October – November 2002, sampling more than 70 plant species of 30 families, including 16 solanaceous species. The results of this survey provide some additional information to the scant knowledge on the phytoseiids from Mato Grosso do Sul. In total, 471 phytoseiids were collected, belonging to 12 Amblyseiinae and two Phytoseiinae species. The most frequent and abundant species was Euseius citrifolius Denmark and Muma, followed by Euseius concordis (Chant). Also, 3,493 tetranychids were found. Tetranychus evansi was found in Aquidauna on Solanum americanum (Miller), associated with E. citrifolius and Typhlodromalus aripo De Leon; in Corumba, on S. americanum associated with E. concordis and Neoseiulus idaeus Denmark and Muma; and in Dourados, on Solanum lycopersicum (L.), associated with E. citrifolius, Proprioseiopsis mexicanus (Garman) and Proprioseiopsis ovatus (Garman). However, none of the phytoseiids found are considered to be a promising biological control agent of T. evansi, based on both their inconsistent association with the pest and on available information about each species.