The first Viva Palestina convoy left London on February 14, 2009, traveling through several countries in Europe and North Africa before arriving in Gaza through the Rafah crossing in Egypt on March 9.

The Viva Palestina convoy had planned to travel to Gaza through the Rafah crossing in an attempt to challenge the Egyptian government to open the crossing, which has frequently been closed because of security concerns. The convoy first encountered some resistance in Egypt, with Egyptian authorities barring the convoy from passing into Gaza and anti-Hamas demonstrators hurling stones and bricks at the convoy, as well as vandalizing several vehicles with anti-Hamas graffiti. Ultimately, on March 9 the convoy was allowed to pass through the Rafah crossing.  (At his speaking appearances in the U.S., Galloway frequently criticized the Egyptian government, describing the situation in Gaza as an "Arab siege" and calling on Americans to challenge Egypt like Viva Palestina had by organizing an American-organized Viva Palestina convoy.)

When they arrived in Gaza, the convoy gave more than one million pounds in aid (the equivalent of approximately $1.5 million in U.S. dollars) and 110 vehicles, including 12 ambulances and a fire engine, directly to the Hamas government. Galloway personally donated three cars and 25,000 pounds to Hamas. At a press conference in Gaza announcing the donations, Galloway openly stated, "We are giving you now 100 vehicles and all of their contents, and we make no apology for what I am about to say. We are giving them to the elected government of Palestine."

While in Gaza, Galloway was warmly welcomed by Hamas officials and met with Prime Minister Ismail Haniyeh who gave Galloway an honorary Palestinian passport. Galloway reportedly praised the Palestinian "resistance" and condemned Israel's offensive against Hamas in Gaza, calling it a "genocidal aggression."