The Middle East situation posed a dilemma for the Ceausescu government, which sought to maintain relations with both sides of the conflict. In 1969 Romania announced an agreement to elevate its relations with Israel to the ambassadorial level, while continuing to voice support for "the struggle of the Arab people to defend their national independence and sovereignty" and calling for a negotiated settlement of the conflict.

The Ceausescu regime maintained good relations with both Egypt and Israel and played an intermediary role in arranging Egyptian President Anwar as Sadat's visit to Israel in 1977. In the following years Romania maintained contacts with all parties in the conflict and cautiously endorsed the Camp David Accords, in contrast with the Soviet Union and other East European countries. In later years, Romania called for a global approach to the Middle East crisis that would involve all interested parties, including the PLO. Ceausescu offered to act as an intermediary and met several Arab leaders including PLO chairman Yasir Arafat. Some observers believed Ceausescu's intermediary efforts were designed to gain access to new sources of Middle East oil to compensate for the suspension of Iranian oil deliveries.

After the late 1970s, Romania advocated a peace plan featuring four points: Israeli withdrawal from all Arab territories occupied from June 1967, including East Jerusalem and southern Lebanon establishment of an independent state governed by the PLO guarantees for the security of all states in the region and convocation of an international peace conference, with representatives from the PLO, the Soviet Union, and the United States. Although Israel rejected all four points of the plan, it continued to maintain good relations with Romania.

After 1985 relations with Israel gradually deteriorated. Although the countries continued to exchange high-level visits, they failed to make major breakthroughs. Romania continued to insist on Israeli concessions, including direct negotiations with the PLO. In August 1987, Prime Minister Yitzhak Shamir of Israel, after nine hours of talks with Ceausescu in Bucharest, reported no progress on the issue of Middle East negotiations. A few months later, Ceausescu invited representatives of the PLO and the Israeli-Palestinian Dialogue Committee to a meeting in Romania, but that discussion too bore no fruit.

Relations with the PLO were generally good, and Arafat and other high-ranking PLO officials frequently travelled to Bucharest. The Romanian media described Arafat as a personal friend and comrade of Ceausescu. Between November 1987 and December 1988, Arafat met with Ceausescu five times. The PLO opened one of its first diplomatic offices in Bucharest, and several bilateral agreements were concluded, some of which reportedly offered the PLO educational and even military training facilities in Romania.

Data as of July 1989