
Fue la expedición de Alejo García, quien había llegado a Buenos Aires con Juan Diaz de Solís, la que exploró por primera vez las tierras del Paraguay. Entre 1521 y 1525, García atravesó la región hasta llegar a los Andes. Otra expedición, encabezada por Sebastián Caboto, remontó los ríos Paraguay, Paraná y Pilcomayo, entre 1527 y 1528. El 15 de agosto de 1537, Juan Salazar de Espinosa, miembro de la expedición de Pedro de Mendoza, funda un fuerte a la orilla del río Paraná. Lo llama Nuestra Señora de la Asunción. Los guaraníes colaboraron en la construcción del fuerte, origen de la futura capital, y ofrecieron a los españoles sus hijas y hermanas para que las tomasen por esposas. No hubo, como en otras colonias, discriminación respecto de los mestizos, quienes desde un comienzo gozaron en Paraguay del mismo estatus que los españoles, y tomaron parte activa en las expediciones que partían de su territorio. España tenía especial interés en que esta zona del continente fuese explorada y colonizada, para detener el avance de los conquistadores portugueses que llegaban desde Brasil. Las expectativas de la metrópoli contribuyeron a ensanchar las dimensiones de la colonia, que llegó a ser conocida como Provincia Gigante de las Indias ya que abarcaba, al menos en teoría, desde las Guayanas hasta Tierra del Fuego, y desde el Atlántico hasta Chile y Perú.