* Islamist threat raises prospect of new front in insurgency
* Warning is from group that claimed attack on tourists
* Group poses new challenge to Egyptian government
* Germany issues travel warning for visitors to Egypt
* Militants massacred tourists at temple in 1997 (Adds attack on soldiers)
By Shadia Nasralla and Michael Georgy
CAIRO, Feb 18 (Reuters) - A militant Islamist group has warned tourists to leave Egypt and threatened to attack any who stay after Feb. 20, raising the prospect of a new front in a fast-growing insurgency in the biggest Arab nation.
The Sinai-based Ansar Bayt al-Maqdis group, which claimed responsibility for a suicide bombing that killed two South Korean tourists and an Egyptian on Sunday, made the statement on an affiliated Twitter account.
"We recommend tourists to get out safely before the expiry of the deadline," read the tweet, written in English, which Egypt's prime minister said on Tuesday aimed to undermine the political process begun after an army takeover in July.
Ansar Bayt al-Maqdis has said that it does not post statements on social media sites, but statements that appeared on the Twitter account in the past have afterwards surfaced on jihadist websites which the group says it does use.
Islamist militants have killed hundreds of policemen and soldiers since the army deposed Islamist president Mohamed Mursi seven months ago, but Sunday's attack on a tourist bus marks a tactical shift to soft targets that could devastate an economy already reeling from political turmoil.
State television quoted Prime Minister Hazem el-Beblawi as saying Ansar was a threat to tourists. It aimed, he said, to derail the roadmap to elections unveiled by the army when Mursi's fall provoked the bloodiest internal crisis in Egypt's modern history.
Ansar has said it was behind Sunday's suicide bombing near the resort of Taba, which revived memories of an Islamist insurgency in the 1990s including a 1997 bloodbath at Luxor, when 58 foreign tourists and four Egyptians were killed at a pharaoh's temple.
On Monday, Germany's foreign ministry changed its travel advice, telling travellers to be cautious about going to Egypt.
It specifically discouraged travel to the Nile Delta outside the urban centres of Cairo and Alexandria and to the Nile Valley south of Cairo to north of Luxor.
Egypt's Western allies had hoped the uprising that toppled president Hosni Mubarak in 2011 would bring political and economic stability to a country at the heart of the Arab world.
Instead, turmoil has gripped the nation of 85 million, which has a strategic peace treaty with Israel and controls the Suez Canal, a vital global shipping lane.
In another sign of instability, an explosion wounded four Egyptian soldiers in the Sinai on Tuesday, state-run Al Ahram newspaper reported on its website.
Tourism was a major employer and accounted for more than 10 percent of gross domestic product before the revolt. Visitors are again sharply down since army chief Abdel Fattah al-Sisi deposed Mursi, Mubarak's successor.
Ansar Bayt al-Maqdis, Egypt's most active Islamist militant organisation, has threatened to topple the interim government installed by Sisi, who is expected to run for president.
The Egyptian state and militants are old foes. Islamist-leaning soldiers assassinated President Anwar al-Sadat in 1981 mainly because of his peace treaty with Israel. It took Mubarak years to put down the 1990s insurgency which targeted senior government officials and foreign visitors, gutting tourism.
Ansar enjoys tacit support from at least some of the marginalised Bedouin community and smugglers in the Sinai. This has enabled them to survive several army offensives in the largely lawless peninsula.
"Ansar Bayt al-Maqdis poses the most formidable security threat in current-day Egypt," said Anthony Skinner, Middle East and North Africa director at risk analysis firm Maplecroft.
"This is not only reflected in the attack on the tourist bus in Taba last weekend, but also in the series of bombings in the Nile Valley and Nile Delta regions."
In one of the boldest attacks claimed by Ansar, a car bomb killed 16 people at a security force headquarters in the Delta city of Mansoura on Dec. 24. The attack was claimed on the same Twitter account before jihadist sites carried the statement.
While security forces have crushed Mursi's Muslim Brotherhood, a political movement that had forsworn violence decades ago, Ansar Bayt al-Maqdis has become more brazen.
The group has extended its reach beyond the Sinai to cities including Cairo, where it claimed responsibility for an assassination attempt on the interior minister.
The group also said it was behind the shooting death of an Interior Ministry general.
"This statement, if genuine, would add tourism quite explicitly to the target set already outlined by Ansar, which includes security forces and economic interests of the state and the army," said Anna Boyd, an analyst at London-based IHS Jane's.
An army source told Reuters that the latest attacks were a reaction to a military offensive which was hurting militants. "They are breathing their last breath," he said. (Additional reporting by Omar Fahmy, Asma Alsharif and Yasmine Saleh; Editing by Giles Elgood, David Stamp and Alastair Macdonald)