Официальные двусторонние советско-палестинские отношения установлены в 1974 году, когда в Москве было открыто представительство Организации Освобождения Палестины. 18 ноября 1988 года СССР официально признал Государство Палестина, провозглашенное тремя днями ранее в Алжире на сессии Палестинского национального совета. В январе 1990 года Палестинское представительство в Москве стало Посольством Государства Палестина, возглавляемым послом.
В августе 1995 году в Газе начало функционировать Представительство Российской Федерации при Палестинской национальной администрации (ПНА). В марте 2004 года Представительство было переведено в Рамаллу.
После образования в мае 1994 года Палестинской национальной администрации (ПНА) российско-палестинские отношения вышли на межгосударственный уровень.
Россия стала первой зарубежной страной, которую 30 января — 1 февраля 2005 года посетил избранный глава Палестинской национальной администрации Махмуд Аббас. Всего с 2005 года по 2013 год состоялось 10 визитов Махмуда Аббаса в Россию.
Программы его визитов в 2008-2013 годах включали посещение Чечни, Дагестана, Татарстана, Башкортостана, Чувашии и Карачаево-Черкессии.
29 апреля 2005 года президент РФ Владимир Путин стал первым действующим руководителем РФ, посетившим Палестинскую автономию. В ходе переговоров Владимира Путина с Махмудом Аббасом российская сторона подтвердила, что "продолжит оказание помощи Палестине в становлении собственной государственности", в "развитии экономики, в том числе в секторе Газа".
Отдельная встреча лидеров состоялась в феврале 2007 года в Аммане (Иордания) в рамках ближневосточного турне Владимира Путина.
18 января 2011 года состоялся рабочий визит президента России Дмитрия Медведева в Палестину (в Иерихон). На переговорах обсуждалось ближневосточное урегулирование, ситуация в регионе, перспектива созыва мирной конференции по Ближнему Востоку в России. Кроме того, обсуждались проблемы экономической сферы, в т. ч. торговля, инвестиционные проекты, туризм и сельское хозяйство.
26 июня 2012 года прошел второй рабочий визит президента РФ Владимира Путина на палестинские территории. В Вифлееме в резиденции главы ПНА Владимир Путин и Махмуд Аббас обсудили палестино-израильское урегулирование, вопросы восстановления межпалестинского согласия, двустороннего взаимодействия. Было подписано межправительственное соглашение о статусе и условиях деятельности Российского музейно-паркового комплекса в Иерихоне. Владимир Путин и Махмуд Аббас торжественно открыли в Вифлееме Российский центр науки и культуры.
В последние годы российско-палестинские контакты на высшем уровне носят регулярный характер. Лидеры двух стран встречались дважды в 2014 (в январе и июне) и 2015 годах (в апреле и сентябре).
В 2016 году президент Палестины Махмуд Аббас посетил Россию с рабочим визитом 18 апреля. На встрече в Кремле главы государств обсудили актуальные вопросы российско-палестинской повестки дня. Приоритетное внимание традиционно уделялось перспективам палестино-израильского переговорного процесса.
Министр иностранных дел России Сергей Лавров посещал палестинские территории в сентябре 2004 года, октябре 2005 года, в сентябре 2006 года, в июне 2007 года, в марте 2008 года, в феврале 2009 года и июне 2010 года в рамках рабочих поездок по странам Ближнего Востока. В ходе ближневосточного турне в ноябре 2012 года Сергей Лавров встречался с Махмудом Аббасом в Аммане. На регулярной основе в сентябре проводятся встречи Сергея Лаврова с Махмудом Аббасом в Нью-Йорке в период созыва сессий Генеральной Ассамблеи ООН.
Между Россией и ПНА заключены межправительственные и межведомственные соглашения: о сотрудничестве в области образования (1988), о культурном и научном сотрудничестве (1994), о торгово-экономическом сотрудничестве (1998) и о сотрудничестве между Счетной палатой Российской Федерации и Государственным бюро по административному и финансовому контролю ПНА (2008). Однако реализация этих соглашений затруднена в связи с сохраняющейся сложной ситуацией в регионе.
13 апреля 2015 года в рамках визита палестинского президента Махмуда Аббаса в Россию была создана Межправительственная российско-палестинская комиссия по торгово-экономическому сотрудничеству. Этот формат взаимодействия пришел на смену рабочей группе высокого уровня для проведения консультаций по экономическим и инвестиционным вопросам. Сопредседателями комиссии являются министр труда и социальной защиты РФ Максим Топилин и министр национальной экономики Палестины Абир Оде. Первое заседание комиссии прошло 14-15 марта 2016 года в Рамалле.
Минэкономразвития РФ характеризует торгово-экономические связи и инвестиционное взаимодействие с Палестинской национальной администрацией как практически или полностью отсутствующие. Президент Палестины Махмуд Аббас объясняет низкий товарооборот с Россией, оцениваемый примерно в миллион долларов в год, ограничениями, которые вытекают из давних договоренностей с Израилем (Парижское соглашение от 1994 года было заключено в развитие договоренностей о создании Палестинской национальной администрации и определяет согласованные с Израилем рамки ее экономической, в том числе внешнеторговой деятельности).
Динамика развития объемов взаимной торговли между странами в последние годы приобрела поступательный характер: за последние пять лет товарооборот увеличился почти в шесть раз — до 3,4 миллиона долларов в 2015 году.
Ведомства России и Палестины активно взаимодействуют по вопросам образования, культуры и туризма.
Начиная с 1970-х года оказывается помощь в подготовке национальных кадров путем предоставления государственных стипендий на обучение палестинцев в российских вузах за счет средств федерального бюджета.
В октябре 2010 года при содействии Управления делами Президента Российской Федерации было завершено строительство музейно-паркового комплекса (МПК) в Иерихоне. 26 июня 2012 года Владимир Путин и Махмуд Аббас приняли участие в открытии Российского центра науки и культуры (РЦНК) в Вифлееме. Там же был открыт гостевой дом для приема православных паломников. Россия профинансировала ремонтно-реставрационные работы вифлеемской Церкви Рождества Христова. В последнее время заметно активизировало просветительскую, культурную и научную деятельность Императорское православное палестинское общество (председатель Сергей Степашин). Общество проводит большую работу по развитию туризма на палестинских территориях, прежде всего в Иерихоне, Вифлееме, Хевроне и Восточном Иерусалиме.