Teren obecnego Paragwaju został odkryty w roku 1524 przez Portugalczyka Aleixo Garcię i Włocha Sebastiano Caboto, działających na służbie Korony hiszpańskiej. Przyszłą stolicę, Asunción, założył w roku 1537 Juan de Salazar y Espinosa. Prowincję zorganizował dla Korony hiszpańskiej pod koniec lat 30-tych XVI wieku Juan de Ayolas. W ten sposób rozpoczęła się długa historia kolonialna Paragwaju – aż do roku 1811, gdy kraj uniezależnił się od Hiszpanii.

Czasy prekolumbijskie

Do przybycia konkwistadorów hiszpańskich, terytorium wschodniego Paragwaju, tzn. obszar między rzekami Parana i Paragwaj, był zamieszkany przez różne ludy indiańskie, będące w stanie ciągłej wojny między sobą. Ludy te dzieliły się na trzy grupy: pámpidos, lágidos i amazónidos. Nie wiadomo, czy teren jako pierwsi zajęli lágidos, czy też pámpidos. Dokumenty mówią, że w wieku XV amazónidos avá, znani szerzej jako Guarani, zdołali zdobyć rejony północne i wschodnie dzięki swojej przewadze liczebnej i rozwiniętej kulturze materialnej – umieli uprawiać maniok jadalny, kukurydzę i orzeszki ziemne. Znajomość techniki orki pozwoliła im wytworzyć nadwyżki potrzebne do utrzymania stałego wzrostu demograficznego i ekspansji terytorialnej.

Przed Guarani na terytoriach Paragwaju mieszkały ludy myśliwsko-zbierackie z grupy lágidos (np. ašé-guayakí) i pámpidos, wśród których znajdowały się ludy nazywane przez Guarani agace i payaguá.

Według źródeł, pierwszym Europejczykiem, który spotkał Guarani, był Aleixo Garcia – odkrywca i podróżnik portugalski na służbie hiszpańskiej, który uczestniczył w licznych ekspedycjach do Ameryki Południowej. Po wyrzuceniu na Wyspę Św. Katarzyny (która obecnie należy do brazylijskiego stanu Santa Catarina) jako rozbitek w r. 1525, przewodził dużemu oddziałowi Guarani, który, poruszając się wzdłuż rzeki Pilcomayo, dotarł do granic państwa Inków (prawdopodobnie w okolicach Cochabamba). Tam stoczył z sukcesem kilka bitew i zdecydował wrócić na wybrzeże atlantyckie z imponującym łupem w postaci przedmiotów ze srebra i złota. Umarł w drodze, ale pozostawił dla Europejczyków przybywających do Ameryki Południowej opis swoich przygód.

Sojusze między Guarani a Hiszpanami powstawały często i były skierowane przeciwko innym ludom indiańskim, głównie Guaycuru i Mbya, wśród których znajdowali się owi agace i payaguá. Ludy te zostały ostatecznie wytępione – częściowo wskutek ciągłych ataków Guarani i Hiszpanów, a częściowo wskutek własnych zwyczajów, które stawiały ich w konfrontacji na słabszej pozycji – np. u payagua rodzina miała zakaz mieć więcej niż jednego syna.