Relations between Romania and PLO have been strong since the beginning of the Communist regime in Romania in 1947. Relations between Romania and the PLO were established and strengthened under the regime of Nicolae Ceauşescu, who ruled Romania from 1965 until 1989. In 1974 Romania recognized the PLO and a representative office was established in Bucharest. The PLO representative office later became an embassy. During that time many Palestinian militants were trained in Romania and most of the weapons that the PLO used against Israel were made in the Soviet Union and the Warsaw Pact countries including Romania. Even after the Romanian Revolution of 1989 which overthrew the communist regime and established a democratic republic, Romania remained committed to the Middle East peace process and the establishment of a separate Palestinian state. In fact, Romania had maintained bilateral relations both with Israel and the Palestine Liberation Organization and was seen by both sides as a neutral mediator. Romania was one of the first countries to recognize the Palestinian Authority after the Palestinian Declaration of Independence on November 15, 1988. Romania has since maintained relations with the Palestinian Authority and has always supported Palestinians' cause in the United Nations.
The Palestinian President, Mahmoud Abbas, also paid an official visit to Romania in 2008, during his trip to Europe. During his two-day stay in Bucharest, Abbas met Traian Băsescu the President of Romania as well as the then-Prime MinisterCălin Popescu-Tăriceanu, Senate Chairman of Romania Ilie Sârbu, and also leaders of both chambers of the Romanian parliament. President Abbas emphasised the strong relations between the two nations and he noted that it was in Bucharest in 1988 that both Israel and the PLO had held their very first meeting. Earlier in February 2008, the then-Romanian Foreign Minister Adrian Cioroianu paid a visit to the Palestinian territories. During the meeting Cioroianu reiterated the Romanian people's continuing support for the Palestinian cause and the Middle East peace process. Also the Palestinian Authority agreed to never recognize the unilateral declaration of independence by Kosovo on the grounds that it was illegal and that it violated international law.
During the 2008–2009 Israel–Gaza conflict, Minister of Foreign Affairs, Cristian Diaconescu, pointed out Romania's concern about the current situation and has expressed his belief that the cessation of violence and identification of solutions for the humanitarian issues from the Gaza Strip are absolutely necessary in view of resumption of political dialogue. He said that the solution to this crisis may be found only by political means and he has emphasised Romania's preparedness to undertake, in cooperation with the partners from EU and following bilateral actions, the diligences necessary to support the political-diplomatic regulation of this crisis. He also said that, understanding the daily difficulties the population from the Gaza Strip is facing for, the Romanian authorities are available also for the identification of certain solutions to grant humanitarian assistance. During the 2014 Israel-Gaza conflict, The Ministry of Foreign Affairs activated a crisis cell for granting consular assistance to Romanian citizens in the Gaza Strip. Likewise, it was decided the dispatch several consular teams equipped with mobile means of granting consular assistance.