Республіка Парагвай визнала незалежність України 1 квітня 1992 року. Дипломатичні відносини між двома державами були встановлені 26 лютого 1993 року.
Починаючи з 1997 р., Посол України в Аргентині є за сумісництвом Послом у Парагваї. У лютому 2004 р. парагвайська сторона вперше після встановлення дипломатичних відносин між двома державами призначила Посла в Україні за сумісництвом: ним став керівник дипмісії Парагваю у Ватикані Маркос Мартінес Мендіета.
У 2002 р. МЗС України призначило Почесного консула України в Парагваї, яким став відомий парагвайський бізнесмен українського походження Андрес Троцюк. У вересні цього ж року в м. Фрам парагвайського департаменту Ітапуа, де компактно проживають етнічні українці, було відкрите Почесне консульство України.
У квітні 2005 р. в м. Сантьяго-де-Чилі в рамках проведення ІІІ-ї Міністерської конференції Спільноти демократій відбулася перша з моменту встановлення дипломатичних відносин між двома державами зустріч Міністра закордонних справ України Б.І.Тарасюка з главою зовнішньополітичного відомства Парагваю Л.Рашид.
Наприкінці лютого 2006 р. в Києві відбулися перші в історії двосторонніх відносин політичні консультації. Делегацію України очолив Перший заступник Міністра закордонних справ В.Д.Хандогій, парагвайську – Перший заступник міністра закордонних справ Е.Хіменес.
25 жовтня 2007 р. Сенат Національного конгресу Парагваю ухвалив Декларацію №43, відповідно до якої Голодомор 1932-1933 рр. в Україні визнано геноцидом українського народу. Співавтори тексту Декларації – сенатори Е.Камачо та А.Еспінола – Указом Президента України №1169 від 29.11.2007 нагороджені орденами «За заслуги ІІІ ступеня».
Центральною подією 2008 р. у українсько-парагвайських дипломатичних відносинах став перший офіційний візит Міністра закордонних справ Парагваю Р.Раміреса до Києва. Парагвай став співавтором проекту резолюції «Вшанування жертв Голодомору в Україні», ухваленої на 34-ій сесії Генеральної конференції ЮНЕСКО, а Президент Парагваю Ф.Луго направив лист на адресу керівництва Української держави з нагоди відзначення 75-ої річниці Голодомору 1932-1933 років в Україні.
26 квітня 2012 року відбувся перший в історії українсько-парагвайських відносин офіційний візит Міністра закордонних справ України К.І.Грищенка до Республіки Парагвай. У ході візиту були проведені переговори з Міністром закордонних справ Парагваю Х.Л.Кастро, зустрічі з Президентом Парагваю Ф.Луго, Віце-Президентом Парагваю Ф.Франко. Основною метою візиту було поглиблення двостороннього українсько-парагвайського політичного діалогу на високому рівні, у тому числі обговорення актуальних питань у сфері торговельно-економічного та інвестиційного співробітництва, взаємодії в рамках міжнародних організацій. Міністри закордонних справ двох країн підписали Договір про дружбу і співробітництво між Україною та Парагваєм, а також Угоду про співпрацю між Дипломатичною академією України та Дипломатичною і консульською академією Парагваю імені Хосе Фалькона.
Важливою акцією підтримки з боку Парагваю в контексті російської агресії проти нашої держави стало позитивне голосування 1 липня 2016 року за резолюцію 32-ї сесії Ради ООН з прав людини „Співпраця та допомога Україні в галузі прав людини”, у тексті якої було зафіксовано посилання на резолюцію ГА ООН № 68/262 від 27 березня 2014 року «Територіальна цілісність України».
23 квітня 2015 року в Палаті депутатів Національного Конгресу Парагваю було вперше утворено групу дружби «Парагвай-Україна».
Указом Президента України П.Порошенка № 401/2015 від 7 липня 2015 р. Надзвичайного і Повноважного Посла України в Аргентинській Республіці Ю.О.Дюдіна було призначено Надзвичайним і Повноважним Послом України в Республіці Парагвай за сумісництвом. Вручення вірчих грамот Президенту Парагваю О.Картесу відбулось 14 жовтня 2015 року.
Важливою подією двосторонніх відносин стало відзначення 25-ї річниці встановлення дипломатичних відносин між Україною та Парагваєм. З цієї нагоди Посол Ю.Дюдін 24-27 лютого 2018 відвідав Республіку Парагвай. В рамках візиту, окрім традиційних заходів в м.Енкарнасьйон, місці компактного проживання багаточисельної громади нащадків українських переселенців у Парагваї, були здійснені важливі контакти в столиці країни – м.Асусьйон. Відбулись зустрічі з керівництвом МЗС Парагваю, зокрема з Міністром Е.Лойсагою, його заступником Ф.Гонсалесом, керівниками профільних департаментів зовнішньополітичного відомства, а також з представниками законодавчої гілки влади – депутатами Національного конгресу У.Рубіним, В.Хармсом Сеспедесом.
Набуття чинності Договором про дружні відносини і співробітництво між Україною та Парагваєм, яке відбулося напередодні візиту 1 лютого 2018 року, забезпечила сприятливий контекст усіх зустрічей та дозволила співрозмовникам будувати конкретні плани розвитку двосторонніх відносин з урахуванням набуття ними нового статусу.
21 травня 2018 року у Верховній Раді України вперше була створена депутатська група з міжпарламентських зв’язків з Парагваєм. Керівником згаданої групи, до складу якої увійшло 6 народних депутатів України, обрано Б.М.Матківського.
06 липня 2022 року – телефонна розмова Президента України Володимира Зеленського та Президента Республіки Парагвай Маріо Абдо Бенітеса.
Квітень 2023 року