DUP leader Ian Paisley and Ireland's most senior Catholic cleric have described their first formal talks as positive.
The two delegations met at Parliament Buildings, Stormont
Mr Paisley, moderator of the Free Presbyterian Church, met Archbishop of Armagh Dr Sean Brady at Stormont.
Speaking afterwards, Dr Brady described the discussions as "helpful and constructive".
Mr Paisley said they had "a very good and useful exchange of views across a range of issues". Both men shook hands.
The DUP leader said his party looked forward "to further discussions with Archbishop Brady and his colleagues in the coming months".
The meeting came just two days before multi-party talks in St Andrews, Scotland, aimed at brokering a deal on devolution and policing.
DUP said there would be further talks with Dr Brady
Mr Paisley said: "Our topics of discussion were social, economic and political.
"I welcome the opportunity that this meeting has provided.
"We have had a very good and useful exchange of views across a range of issues.
"It is in the interests of everyone to develop the foundations for stability and prosperity for all the people of Northern Ireland."
Dr Brady said it confirmed for him that everyone had a part to play in creating a more stable and prosperous future.
"I firmly believe that such a future is within our grasp if each one of us can find the courage to take account of the needs of the other, and not just those of our own community," he said.
"I think that real peace will come only when we focus on the common good of all of our society and not just on sectional interest."
Dr Brady said he discussed the need to develop support for law and order and he prayed that the coming months would bring "a more democratically accountable and stable society".
The DUP said the meeting was one of a series being held with church leaders.
Mr Paisley's decision to meet Dr Brady was welcomed by nationalists.
BBC Northern Ireland political editor Mark Devenport reports: "I don't think we should be getting ahead of ourselves just yet.
"It's not necessarily going to be the case that this ground-breaking meeting between the Catholic church and the DUP leads immediately to a similar ground-breaking meeting between the DUP and republicans."
The DUP delegation included deputy leader Peter Robinson and MPs Nigel Dodds and Gregory Campbell.
The archbishop's delegation included Bishop Francis Lagan, the auxiliary bishop of Derry, and Father Timothy Bartlett, secretary to the Northern Bishops.
Northern Ireland Political Development Minister David Hanson said he welcomed the meeting as "a positive step".
"I hope it will form the background to some very useful talks that we will have this week in Scotland."
He said he would welcome a meeting between Mr Paisley and Sinn Fein's Gerry Adams, but that it was a matter for the two party leaders.
Meanwhile, the DUP also met the Independent Monitoring Commission on Monday to discuss its latest report on IRA activity.
Mr Paisley accused Secretary of State Peter Hain of "selling deceit" over what was actually being said by the IMC.
He said the discussions with the IMC were "most interesting" and he was "quite amazed by their forthrightness".
The picture of IRA activity - in terms of criminality and other activities - was nowhere near perfect, said the DUP leader.
He said it was quite clear the government were "trying to put words into mouths of IMC".
Last week, the IMC said in its 12th report into paramilitary activity that the IRA had changed radically and some of its most important structures had been dismantled.