His return to Palestinian territories follows an eight-day conflict last month between Hamas and Israel, in which 170 Palestinians and six Israelis were killed. The two sides reached a ceasefire and Israel – whose agents tried to assassinate Mr Meshaal in 1997 – is understood to have given tacit agreement to the visit.
But security was tight in Gaza and Israeli officials were offering no guarantees of safe passage. A foreign ministry spokesman said Israel did not differentiate among Hamas leaders. "Hamas is Hamas is Hamas," said spokesman Yigal Palmor.
Shortly after arriving over the Rafah border crossing from Egypt, Mr Meshaal announced his "re-birth". He then prayed with his deputy, Moussa Abu Marzouk, before embracing and kissing dozens of political, religious and militant leaders. "This is a victory for the Palestinian people and his leadership inside Palestine and outside," said his host, Hamas Prime Minister, Ismail Haniyeh. In a rare display of unity, senior Fatah officials joined the reception committee.
Mr Meshaal has been living in exile since the Six-Day War with Israel in 1967 forced his family to flee, but managed to build Hamas into a strong force from exile. His return reflects a growing regional acceptance for Hamas as the Arab Spring sweeps more sympathetic governments into power.
Under Hosni Mubarak, Egypt had bowed to Israeli demands to block Mr Meshaal's passage into Gaza. But his successors in the Muslim Brotherhood have hardened their stance towards Israel, while offering more co-operation to Hamas.
Mr Meshaal's historic visit has for now papered over deep divisions within Hamas over the Islamic group's future strategy towards Israel and the thorny question of future co-operation with Palestinian President, Mahmoud Abbas, whose Fatah movement governs parts of the West Bank after Hamas expelled them from Gaza in 2007. Mr Meshaal vowed to push for unity – the wish of many ordinary Palestinians in both Gaza and the West Bank. "This is a promise from the leadership of Hamas. We will press ahead with reconciliation to end divisions and to stand united against the Zionist occupation," he said.
Surrounded by dark-suited security men with earpieces, Mr Meshaal inspected the wreckage of the car in which the Hamas military chief, Ahmed al-Jabari, was assassinated by Israel last month. He was also expected to visit the home of Sheikh Ahmed Yassin, the Hamas spiritual leader assassinated by Israel in 2004, before participating in a huge rally today to mark the 25th anniversary of the founding of the Islamic Resistance Movement. He will leave shortly after.
In his first public comments, Mr Meshaal derided Israeli Prime Minister Benjamin Netanyahu for endorsing a failed attempt on his life in Amman in 1997. "This is … my third birth. The first was my natural birth in 1956, the second was in 1997, when there was an attempt by the crazed Netanyahu to assassinate me, and this one on the 7th of December 2012. The fourth birth will be in liberating Palestine, in Ramallah, Jerusalem and Haifa and Jaffa," he declared to an audience of dignitaries, security personnel and media.
Mr Meshaal's wife arrived on Thursday, accompanied by more than a dozen family members and Hamas officials. Leaders of Islamic Jihad had hoped to join the commemoration but Israel said that would be a violation of the ceasefire agreement and threatened to assassinate them if they entered Gaza.
Before his guest's arrival, Mr Haniyeh was asked whether he feared Israel might attempt to kill Mr Meshaal. "We don't rule out any foolish behaviour by the Israelis but our people in its steadfastness, and the resistance with its high capabilities, will make the occupation think dozens of times before committing any foolish step. Under the shadow of our guns, the occupation won't be able to hurt any of our leaders," he declared.
Saturday's rally is not being held on the exact date of Hamas's founding, but on the 25th anniversary of the start of the first Palestinian uprising against Israel. The choice is being seen as a new willingness to seek reconciliation with President Abbas, who hosted King Abdullah of Jordan in Ramallah on Thursday in an apparent attempt to re-direct some of the limelight from Gaza.