The artist, whose chooses to remain anonymous, released an online video entitled "Make this the year YOU discover a new destination", that purports to show him travelling to Gaza by commercial flight and then through smuggling tunnels -- possibly underneath the Egyptian border.
Banksy's latest works were a damning critique of Israel's bombardment of Gaza in July and August as it fought against Islamist militants of Hamas, destroying or damaging more than 100,000 homes and killing nearly 2,200 Palestinians, most of them civilians.
The murals include what appears to be Greek goddess Niobe, weeping in the doorway of a destroyed building, and a giant cat painted on the last remaining wall of a Gaza home playing with a ball of twisted metal.
The owner of the house in Beit Hanun in northern Gaza told AFP he would preserve the mural.
- 'We side with the powerful' -
"The person who drew this image didn't announce themselves, they just came, drew it, and left," said Mohammed al-Shinbari, 29.
"The image will remain here forever. I wouldn't get rid of it or sell it even if the house is built up again from scratch.
"It's a mark of history, and is a painful reminder to me of the destruction of my home," he said, proud that a "world famous artist has come to Gaza to help the Palestinian cause."
Some 100,000 people are still homeless and waiting for houses to be rebuilt, but insufficient construction material is coming through the Israeli-controlled crossings, as an eight-year blockade remains in place.
"The locals like it so much they never leave," read a caption on Banksy's video, in reference to Israel's restriction of the movement of people.
Signup to our newsletter and follow us on Facebook and Twitter!
Most Gazans are not allowed to leave the territory, and fewer than ever are managing to exit via Egypt, which is keeping Rafah, the one crossing not controlled by Israel, closed.
Border tunnels like the one Banksy appears to use for entry to Gaza have mostly been destroyed by the Egyptian army, cutting off crucial supply routes for fuel and materials.
The two-minute film shows children playing next to the cat mural, and entire neighbourhoods razed during the war, during which 72 Israelis and one Thai worker were killed by Gaza militants.
"This cat tells the whole world that she is missing joy in her life," a Gazan man is captioned as saying, although his voice is muffled.
"The cat found something to play with. What about our children?"
It fades out on a wall inscription apparently written by Banksy.
"If we wash our hands of the conflict between the powerful and the powerless we side with the powerful -- we don't remain neutral," it reads in English.
Banksy posted pictures of the works on his website.
Banksy is believed to have started out as a graffiti artist in London, although the artist's identity remains shrouded in secrecy.
His murals have been chiselled out of walls and sold for large sums in the past.
He has also graffitied murals in the West Bank, notably on the wall that makes up a large part of Israel's vast separation barrier.