On 10 January 2006, Adalah sent a letter to the Deputy State Attorney demanding the opening of a criminal investigation against Israeli army commanders and soldiers responsible for the extensive home demolitions executed in the south of Gaza in May 2004 during "Operation Rainbow." The letter specifically named (Reserve) Brigadier General Shmuel Zakai, the commander of “Operation Rainbow,” as an individual who should be investigated and prosecuted for his role in carrying out these home demolitions.

Adalah Attorney Marwan Dalal argued in the letter that, based on evidence gathered and documented by international legal experts, international human rights organizations, and Israeli journalists as well as testimonies given by soldiers, criminal offenses were committed by commanders and soldiers during this operation, that these offenses must be investigated, and that those found responsible must be criminally prosecuted. The Israeli military’s actions constituted grave breaches of international humanitarian law, Adalah stressed, notably of Articles 27, 53, and 147 of the Fourth Geneva Convention (1949); Articles 23(g), 25, and 50 of the Hague Regulations (1907); and Articles 51, 52, and 57 of the First Protocol Additional to the Fourth Geneva Conventions (1977).

From 17 to 24 May 2004, the Israeli army conducted an extensive military operation in the south of Gaza known as “Operation Rainbow.” Shlomi Eldar, an Israeli journalist who witnessed the home demolitions that took place during the operation, documented the actions in a book he published later entitled "Eyeless in Gaza." According to Eldar:

"During that whole operation, I stayed in the neighborhoods along the Philadelphi Road (a strip that separates Gaza from Egyptian territory). I saw people fleeing their houses one moment before the bulldozers came. The threatening D-9 [bulldozer], like a mighty hungry monster, went on, sweeping lines and lines of houses in his ‘teeth'. Women and men ran amok. In one hand, they held a baby or small child, who couldn't cope with the pace of fleeing; in the other, they carried a bag that was packed urgently before they escaped from the fear of the bulldozer. Near one of the trenches just formed stood a family – a father, a mother, and probably the grandpa and grandma too – calling a child who lagged behind to cross the trench. The kid was terrified. He hid his head behind a dirt mound and refused to go on.”

Adalah provided substantial documentation to the Deputy State Attorney with the letter. For example, Adalah submitted a report dated 12 August 2004 written by UN Special Rapporteur Prof. John Dugard, who visited the area of military activity shortly after “Operation Rainbow" ended. Prof. Dugard’s report documented that, during “Operation Rainbow”, the Israeli army destroyed or caused irreparable damage to 167 houses, in which 379 families numbering 2,066 men, women and children used to live. Based on this and other significant findings, Prof. Dugard concluded in his report that, "The time has come for the international community to identify those responsible for this savage destruction of property and to take the necessary legal action against them.”

Adalah also submitted the book-length report of Human Rights Watch entitled “Razing Rafah: Mass Home Demolitions in the Gaza Strip.” According to this report, issued on 18 October 2004, the widespread home demolitions during "Operation Rainbow" were a serious and deliberate action. According to HRW’s report, "During the major May incursions of May 18-24, the IDF destroyed houses, roads, and large fields extensively without evidence that the destruction was in response to absolute military needs, including in the areas of Rafah far from the border."

Further, Adalah also included testimonies of soldiers who took part in "Operation Rainbow" which were published in Ha'aretz on 24 January 2005 and 15 March 2005. In their testimonies, the soldiers stated that "Operation Rainbow" was accompanied by an atmosphere of "unrestrained destruction." They also noted that one of the commanders told soldiers at the concluding meeting held in the aftermath of the operation: "Well done. You proved the IDF knows how to be a cruel army."