The trains crossed on opposite sides of Korea
Historic crossing
The two trains - one travelling from the North and one from the South - each carried 150 invited passengers.
South Korea hailed it as a landmark in relations between the two countries.
But Thursday's crossing remains largely symbolic, the BBC's Charles Scanlon says. North Korea has so far only agreed to a one-off test-run.
For that, our correspondent adds, Pyongyang has demanded a high price.
South Korea has agreed to supply it with $80 million (£41m) worth of economic aid for the development of light industry.
'New era'
Hundreds of people gathered at Munsan station in west South Korea to cheer the five-carriage train as it set off on the 25km (16 miles) trip to Kaesong, across the heavily-armed border.
Firecrackers and white balloons were set off and crowds waved white-and-blue "reunification flags".
KOREAN BORDER Heavily fortified border has separated the two Koreas since 1950-53 war 240 km long and 4 km wide, the DMZ takes up about 5% of the Korean peninsula N Korea has 1.1m man army, S Korea and US forces total more than 700,000
In pictures: Train crossing History of Korean War
On the eastern side, children bearing flowers welcomed the North Korean train as it arrived at Jejin station. One carriage carried a banner reading: "The train once boarded by great president Kim Il-sung".
Each train carried 150 passengers from both Koreas - and included celebrities and politicians.
Passengers on the South Korean train said they were warmly received in the North, while female cabin attendants in military uniforms on board the North train posed for pictures upon arrival at the station in the South.
One of those on board the North-bound train was a conductor who made one of the last railway crossings before they ended because of the 1950-53 Korean War.
"I wish I could operate this train myself," Han Chun-ki, 80, said. "I never thought this day would come".
South Korean Unification Minister Lee Jae-joung expressed his hope that the crossing could herald a new era in North-South relations.
"This will be a turning point for overcoming the legacy of the Cold War era, tearing down the wall of division and opening a new era for peace and reunification," he said.
A North Korean official, Kwon Ho-ung, said both nations "should not be derailed from the tracks" towards unification.
However, not everyone welcomed the event.
A small number of protesters - mainly relatives of South Koreans allegedly abducted by the North following the war - gathered at Munsan.
"I wish the train would come back with my son if he is still alive," a tearful Lee Kam-shim, 72, told the Associated Press.
Border tension
The South has long pushed for a railway connection with the North - not only as a way of improving links with its neighbour, but also to establish better transportation links to China and beyond.
But the secretive Communist country has been less enthusiastic, and previous talks have collapsed as Pyongyang has sought to extract concessions on other issues, such as a disputed sea border.
The train from the North was welcomed by flag-waving onlookers
Thursday's historic crossing was made possible after the North's military agreed last week to provide security across what is the world's most heavily fortified border.
The two sides are still technically at war - having never signed an official ceasefire at the end of the Korean War.
But there have been concerted efforts, particularly by the South, at reconciliation in recent years.
The railway tracks - which run alongside roads across the border - were built and maintained by South Korea part of recent reconciliation projects.
And landmines and tank traps were cleared from the narrow border strip two years ago when the lines were reconnected.
Diesel locomotive of the type that crossed from south to north
For the first time in 56 years, two passenger trains crossed the border between North Korea and South Korea.
Before today, no trains made the trip between the north and the south since the Korean War divided the once-unified Korea. 

Riding on rails built by South Korea several years ago, the train traveled from Munsan in the south to Kaesong in the north. The train was granted access to the demilitarized zone since 1951, the heavily guarded border between North and South Korea. Meanwhile, from the north a train traveled from Kumgang to Jejin. Each train carried 150 specially invited passengers.

"Today the heart of the Korean peninsula will start beating again," South Korean Unification Minister Lee Jae-joung said.

Although largely symbolic, the rail connection is seen as an important step in thawing relations. To date, North Korea has approved only this one trial run of the trains.