Half a century ago, before the two Koreas were divided by war and Cold War ideology, Pyongyang - now the capital of North Korea - was a thriving center for Christianity and known as the Jerusalem of Korea.
But today, North Korea has been added to a US State Department list of countries which Washington says denies religious freedom to its people.
Anyone can become a Christian if they want to and everyone is free to practice their faith
Chang Sung Bok
Pastor at Pongsu church
North Korea's constitution grants freedom of religious belief, but also states that no-one should use religion as a means to drag in foreign powers or to destroy the state or social order.
Three churches operate in Pyongyang - but human rights groups say that outside officially sanctioned churches, North Korean Christians can face harsh penalties.
There are about 12,000 practising Christians in North Korea, and those who cannot come to church are able to worship in small groups in homes.
Foreign delegations
The pastor Chang Sung Bok at Pongsu Church in Pyongyang insists there are no controls.
"There's no religious persecution. Anyone can become a Christian if they want to and everyone is free to practice their faith," he said.
There were no signs of Christmas decorations
"And there are more than 500 house churches throughout the country where Christians can go to pray," he added.
To counter the critics, officials are allowing more foreigners to visit its churches - including a South Korean Christian delegation, which I joined.
"At a time when inter-Korean relations are facing difficulty, we Christians should work harder than ever. By building contacts with North Korea, we can help to bring peace to the Korean peninsula," said Reverend Kim Dong Wan, a member of the delegation.
Reunification hope
Reverend Bok agrees with his counterpart from the South that the visits are a good thing.
"Through these visits we exchange our views mainly on the peaceful reunification of our country. We pray for the reunification and through this prayers, we hope reunification can come closer," he said.
The constitution says there is religion, but it is only on paper
Kim Sang Chul
Human rights campaigner
But upon returning to South Korea, Reverend Wan explained that despite his visits to churches in the North it was still impossible to verify just how free people were to worship.
"Its impossible to tell how much they represent genuine opportunities for worship, or are simply showcase churches for visitors. I'm not given the chance to talk to any of the congregation," he said.
From what I witnessed at Pongsu church, there was little sign of spontaneity. Nor were there any signs of festive spirit - though I was told that the church is decorated on Christmas Day.
Crackdown
Critics - including the US State Department - believe independent religious activity is banned in the North.
Kim Il-Sung is worshipped as a God in North Korea
They say there are many reports of crackdowns against Christian members of underground churches and those who have had contact with foreign missionaries.
Kim Sang Chul is Secretary General of a South Korean non-governmental group helping defectors, which is affiliated to a church group in Seoul.
"You know in North Korea there is a God named Kim Il-Sung. When one believes in God, not in Kim Il-Sung or his successor, Kim Jong-Il, it means it is real betrayal or defection against the nation," he said.
"The constitution says there is religion, but it is only on paper," he added.
Fraught relations
Churchgoers, I notice, do not openly wear the badge that all North Koreans prominently display - depicting the late Kim Il-Sung, or his son, the current leader, Kim Jong-Il.
But allegations of religious repression in North Korea are hard to verify - its one of the most secretive countries in the world.
The US State Department report has been angrily rejected by North Korea's official media - and it is likely to increase already tense relations between the two countries.