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. During these two visits, both nations signed agreements on scientific, technical and cultural cooperation; banking, trade and investments; to combat illegal smuggling and the removal of visa requirements for citizens of both nations.
In 2014, two-way trade between both nations amounted to $330 million USD. Mexico's exports to Paraguay include: tractors, automobile parts, beer, tequila, cement and machinery while Paraguay's exports to Mexico include: tung oil, sugar, cassava, fruits and textiles. Since 2013, both nations have been negotiating a free trade agreement with one another.