Первые контакты на дипломатической основе между Российской Империей и Республикой Парагвай состоялись еще в XIX веке, а именно в 1862 во времена правления парагвайского президента Франсиско Солано Лопес и российского императора Александра II.
Официальные дипломатические отношения были установлены в 1909 году с подачи Сеньора Маврикио Прозор первого Чрезвычайного Посланника и Полномочного Министра Российской Империи в Республике Парагвай.
С падением Российской Империи дипломатические связи были прерванны на несколько десятилетий.
14 мая 1992 года правительство Республики Парагвай и Российской Федерации возобновили дипломатические связи посредством соответствующих дипломатических поручений в Монтевидео, Уругвае.
В 2013 году состаялась двадцать первая годовщина обновленных дипломатических связей, характеризующихся динамичным развитием и плодотворным двухсторонним и многосторонним сотрудничеством в областях политики, экономики, торговли и культуры.
За время двадцати одного года дипломатического сотрудничества состоялись официальные встречи первых лиц двух стран, так в 2007 году министр иностранных дел России Сергей Лавров посетил Республику Парагвай с официальным визитом, а в 2010 году был совершен ответный визит министра иностранных дел Парагвая Эладио Лоисагой в Российскую Федерацию.
Также, министры двух стран определили совместное развитие по трем направлениям; было подписано шесть двухсторонних договоров, затрагивающих различные сферы двустороннего взаимодействия: договор о дружбе, торговле и сотрудничестве между Дипломатическими академиями в области культуры, науки, образования и спорта; соглашение о безвизовых поездках по дипломатическим и служебным паспортам.
Последним из установленных договоров между странами стало Соглашение об условиях отказа от визовых формальностей при взаимных поездках граждан, подписанный 25 сентября 2013 года в Нью-Йорке министром иностранных дел Парагвая Эладио Лоисагой и его российским коллегой Сергеем Лавровым. Данное соглашение станет важным юридическим инструментом, который облегчит перемещение соотечественников обеих стран и будет способствовать увеличению туризма и коммерческой активности в обоих направлениях.
Несколько проектов соглашений сейчас находятся в стадии переговоров. Они затрагивают такие темы как: вопросы экстрадиции, судебное сотрудничество по уголовным делам, перемещение заключенных, сотрудничество в таможенной, технической, военной и энергетической сферах, а также в горной промышленности.
Российская Федерация и Республика Парагвай разделяют принципы свободы и демократии при главенстве Международного права и фундаментальных начал Декларации Организации Объединенных Наций, которая признается самой важной из международных систем для поддержания мира и безопасности, многосторонние основания которой должны быть укрепленны и приведенны в соответствие с новой реальностью мировой политики.
Таким образом, две страны признают важность международного сотрудничества как инструмента для предотвращения и не размножения оружия массового уничтожения; для борьбы с терроризмом, международной организованной преступностью и незаконным движением наркотиков и оружия.