Historically, both countries were part of the Spanish Empire until the early 19th century. Mexico was part of the Viceroyalty of New Spain while Paraguay was part of the Viceroyalty of the Río de la Plata. Soon after independence, Mexico established a non-resident embassy concurrent to Paraguay from Buenos Aires in 1831. In 1901, Paraguay established a diplomatic mission in Mexico City with Mexico reciprocating the gesture three years later in 1904. In 1943, both diplomatic missions were elevated to the rank of embassies. 
During the presidency of Alfredo Stroessner, Mexico maintained diplomatic relations with Paraguay despite international condemnation of the Paraguayan government. Mexico applied its foreign policy known as the Estrada Doctrine. A few years after the removal of President Stroessner from power; in 1992, Mexican President Carlos Salinas de Gortari paid a state visit to Paraguay. In 1997, Paraguayan President Juan Carlos Wasmosy also paid a state visit to Mexico. Since then, there have been several presidential visits to each other's nations.