About 600 people, all refugees registered with UNRWA, the UN agency for Palestinian refugees, live in the Ein Jwesia section of al-Walaje. Now, many of these Palestinians are concerned that they will lose their homes and land.
"I have two demolition orders against my home," said Amin al-Atrash, from Ein Jwesia.
"About 30 houses have already been destroyed in the village over the years," he added.
As the residents are registered refugees, their case has been closely followed by UN agencies, although there is concern among aid workers that the efforts are "too little, too late".
Shlomo Dror, from the Israeli minister of defence, said the houses are being demolished as they are illegal. "It's the law," he said.
He was certain though that the villagers would be able to continue accessing their land.
"They'll get permits," he said. "We always set up options for people who are disconnected from their land."
The villagers, however, say they would rather be able to access their land without bureaucratic complications, and uncertainties about how the system will work in the future.
"The situation of those living in Al-Walaje is of grave concern," said one UNRWA official who closely follows the village's case.
"These are 1948 refugees [those who left when the state of Israel was created]. They stand to lose everything all over again and to go through the trauma of yet another displacement if their homes are demolished," she [the official] added.
The 1948 war divided the village in two, with half - the residential part, known now as "old Walaje" - falling under Israeli control.
Some 600 residents fled the area, while about 1,000 people restarted their lives on their agricultural land nearby, which was then under Jordanian auspices.
"Everyone promised us we would be able to return to our village," said al-Atrash. "But we were never allowed to."
In 1967 Israel annexed half of the remaining parts of Walaje along with East Jerusalem, which it considers to be an inseparable part of the Jewish state.
Since the people of Walaje hold West Bank ID cards, they are not allowed into Jerusalem without Israeli-issued permits. However, as significant parts of Walaje are inside municipal Jerusalem, the villagers face an absurd situation.
"People have been arrested for being inside Jerusalem without the right permits, even when they were in their own homes," explained al-Atrash.
Demolitions began in 1985
Problems began for the residents in 1985, when Israeli authorities began to demolish homes. The problems further escalated in 2004, when plans to build a new Jewish settlement, as well as the barrier, on the parts of Walaje annexed into Jerusalem were announced.
"Most of the agricultural land will be behind the wall and disconnected from the village," said Shawki Issa, a lawyer who helped fight land confiscation orders.
"This village has no future like this, surrounded by settlements and walls," he said.
The new settlement, Givat Yael, is planned to surround the village on three sides, while another settlement, already built, blocks it on the fourth side.
"What this [new] settlement will do to their lives, it will choke them completely, ruin the peaceful existence of this village," said Meir Margolit, who was a member of the Jerusalem City Council, and now works with the residents on their housing rights.
Al-Atrash says that already many young people are leaving the village because there simply are no places for them to live as open land for building is now very limited.