In 2001, Kobi Farhi was sitting at his desk in Tel Aviv, checking his email. Farhi was the lead singer of Orphaned Land, an Israeli heavy metal band which at that time had not played together since 1994. Whatever was on Farhi's mind that day, it was probably not their music.

Opening his email account, he spotted an unusual message in his inbox. "I recognised that it was an Arab name, and I opened it up," says the soft-spoken Farhi. "It contained a video file. I opened it, and I didn't see a face or anything like that, but I could hear clearly that this was one of our songs playing in the background. I just saw the arm of a guy. He was pulling the sleeve of his T-shirt up, and I saw that he had a tattoo of Orphaned Land on his arm."

The sender, a Jordanian named Ez (Farhi declines to reveal any more information about him), later became friends with the band. And Farhi certainly knew the significance of that tattoo. As an Arab, Ez was risking imprisonment and possibly torture by tattooing onto his body the name of a band that was to all intents and purposes illegal in his country.

The knowledge that Orphaned Land - a band of Israeli Jews - had a secret fan in an Arab country ignited Farhi. "I phoned the band members," he says, "and I told them that we must have a meeting right away. When they came to my house, I showed them the video, explaining to them that this is an Arab guy who made a tattoo of Orphaned Land when we hadn't existed for six years. And I told them: 'What could be more important than this.'"

Nearly 10 years later, Orphaned Land are still going strong, plying their brand of heavy metal to festivals across the world. But this is not just a story about the rebirth of a band. Orphaned Land did not just have one lone devoted fan in the Middle East, but hundreds, in Iran, Saudi Arabia and elsewhere, many with tattoos like Ez's. The Israeli musicians had discovered that even in countries where heavy metal is virtually illegal, bands have followers who defy the authorities to listen to their favourite music.

Our fans always had to buy our CDs secretly. They had to smuggle them from Europe

"They always had to buy our CDs secretly," says Farhi when asked about how his fans accessed his band's music. "They had to smuggle them from Europe. CDs are not available in the shops in these countries. The authorities see all the skulls [a popular heavy metal motif] and names of bands like Slayer and they think it's Satanism."

Farhi says he and his current bandmates - Uri Zelha, Yossi Sassi Sa'aron and Matti Svatizky - have met legions of their fans throughout the region. Their first concert after their reunion in 2001 was in Turkey.

"After the band got back together, we scheduled a show in Turkey because we had an open invitation to play there. Just having the band again, playing a show, meeting these Muslim fans - we even had 20 travelling with us. The whole journey was filmed for a documentary that was later broadcast on Israeli national TV. The crowd was completely insane, singing along with us, clapping, jumping. It was a religious experience."

Countries like Iran, Syria, Pakistan and Saudi Arabia do not ban music. Rather, for the most part, strictly religious governments in these countries censor it. Music can still be performed and played, but not before it has gone through a series of panels to ensure that it is compliant with government and religious guidelines. The number of contemporary music acts that get released is small.

Freemuse, an independent organisation for the freedom of musical expression, says that in Iran, for example, there are three committees overseen by a the Ministry of Culture, which determine what music is fit to be played. But some "illegal" music slips through the net and gains a following. Zareen, a journalist and rock fan living in Tehran, says that over 140 people were recently involved in organising a music festival without the government's knowledge. "There have for years been a series of underground music concerts, and albums are often released in secret," she says. "We are working hard on this, as we are devoted to underground music."

Orphaned Land are an unusually provocative band. They mix multiple religious messages and iconography in their music, and are unafraid to combine traditional elements with ultra-heavy metal. The song Sapari, which opens their 2010 album The Neverending Way Of Orwarrior, mixes metal guitars with a 400-year-old traditional Jewish poem written by Sa'adia ben Amram.

The music of the band is also heavily informed by the diverse background of the players. They may all share the common thread of Judaism, but they have family origins in Iraq, Egypt, Spain, Turkey and Greece, and this mix of backgrounds can be heard in the way they make their music. On a previous album, Farhi sung in Arabic - working for a month with a Syrian friend to correct his diction and pronunciation.

The band appear to relish causing controversy. For the new album, they released a promotional photograph of themselves which combined Christianity, Judaism and Islam in one multi-denominational image. The photo drew criticism from the metal community, and Farhi says that although he knew and expected that the photo would divide fans, he is not sure it was interpreted the way it should have been.

"We got some bad responses to our photo," he says. "Extremist Jews don't support me looking like Jesus Christ, or seeing me with Arab people. And the Jews in our photo, they are praying like Muslims, and the Muslims are praying like Jews. They think we did it to provoke or make them angry. This is untrue - it was to send a message - 'Why can't you just get along?'"

Farhi is hopeful that his band - and others - can continue to make an impact in the region. "I think that music is a very, very strong tool. Governments are far from understanding that - they think that weapons are a strong tool. Everyone in the world seeing the news coming from the Middle East and Israel - the news is always bad. I'm always telling them - listen, Orphaned Land is just a band. But the results that this band achieved, having Arab followers without any of your help. Just imagine what you could achieve."