El Mundo correspondent Javier Espinosa, 49, and freelance photographer Ricardo Garcia Vilanova, 42, were “freed and handed over to the Turkish military”, the Spanish newspaper said on its website.
Espinosa called El Mundo's offices on Saturday evening and said they were in good health, it added.
“Pure happiness,” wrote Espinosa's girlfriend, the journalist Monica Garcia Prieto, on Twitter early Sunday, without giving further details.
“Their relatives are feeling excitement and joy because this puts an end to a nightmare that has lasted six months,” a spokesman for their families, Gervasio Sanchez, told AFP.
Espinosa and Vilanova were seized on September 16 as they tried to cross the Syrian border to Turkey, the latest of scores of journalists captured while covering Syria's civil war.
There was no immediate word on Sunday on whether any demands were made by their kidnappers or any ransom paid.
The Spanish Defence Ministry told AFP a military aeroplane bringing the two journalists back from Turkey was scheduled to land in Madrid about 4:00 pm (1400 GMT).
El Mundo identified the captors as members of the Islamic State of Iraq and the Levant, a jihadist faction in Syria with roots in Al-Qaeda's Iraqi affiliate.
The group has fought against the regime of Bashar al-Assad in Syria but has also been battling other rebel groups.
The newspaper had kept the kidnapping quiet until December while it contacted the captors via intermediaries. It said at that time that the kidnappers had made no demands.
“It has been a hard few months. We knew the wait would be long but you never get used to it,” said the director of El Mundo's international pages, Ana Alonso Montes, on Sunday.
“You never know when the moment of liberation will come, although we never doubted it would,” she told national radio.
- Reporting Syrian bloodshed -
Award-winning reporter Espinosa has been a Middle East correspondent for El Mundo since 2002 and is based in Beirut.
Like Vilanova, he has covered some of the most dangerous points in the Syrian conflict, including the siege of Homs in February 2012.
On February 22 he escaped that bloodbath in which human rights groups said 700 people were killed and thousands injured, and made it back to Lebanon a week later.
Among those killed in Homs were two other Western journalists: US reporter Marie Colvin and French photographer Remi Ochlik.
Espinosa wrote of his escape from the city, under fire among a crowd of wounded refugees, in a compelling reportage published in March 2013.
“We believe the Syrian people need our work, and that we must live up to our responsibility,” said Prieto, who is also a prize-winning journalist, in December.
An online forum that frequently features statements from jihadists had also called on the militants to free the two.
The Honein jihadist forum said the two journalists were a “good hand for advocating our issues in Iraq and Syria, and carrying the silenced truth”.
Garcia Vilanova has contributed to Agence France-Presse and other world media such as the New York Times and the Washington Post.
Media rights group Reporters Without Borders ranks Syria as the most dangerous country in the world for journalists.
A third Spanish journalist seized separately in Syria in September, Marc Marginedas, a correspondent for the Catalan daily El Periodico, was freed early this month.
French, US and Syrian journalists are among the others still missing in Syria.