The Greek Cypriot vote kills a UN-backed plan to end the 30-year division of the island, television exit polls said.
"We forecast a vote of up to 75% against," said an analyst for the Greek Cypriot Mega Channel.
Other Greek Cypriot TV exit polls agreed.
Such a result would mean only the wealthier 600,000 Greek Cypriots on the 800,000 population island will join the European Union on 1 May.
The Turkish Cypriot vote was 60% for and 40% against the United Nations plan, TV exit polls there said.
The Greek Cypriot vote went against urgent appeals from the United Nations, the United States and the European Union to solve a diplomatic conundrum that has implications far from Cyprus's shores including Turkey's own hopes of joining the
The EU executive said on Saturday it deeply regretted the overwhelming rejection by Greek Cypriots of a plan to reunify their divided island, but praised Turkish Cypriots for their desire to solve the island's problem.
"The European Commission deeply regrets that the Greek Cypriot community did not approve the comprehensive settlement of the Cyprus problem... A unique opportunity to bring about a solution to the long-lasting Cyprus issue has been missed"
EU executive statement
"The European Commission deeply regrets that the Greek Cypriot community did not approve the comprehensive settlement of the Cyprus problem, but it respects the democratic decision of the people," the EU executive said in a statement.
"A unique opportunity to bring about a solution to the long-lasting Cyprus issue has been missed."
Cyprus was wracked by ethnic violence in the 1960s and split by a 1974 Turkish invasion after a Greek Cypriot coup tried to unite the island with Greece.
The Greek Cypriots in the south of the island believe the UN power-sharing plan did not give them enough territory and guarantees about withdrawal of 30,000 Turkish troops stationed in the north since the invasion.
"I voted against the plan," said Greek Cypriot shopkeeper Loucas Constantinou, 38. "I am at peace with my conscience."
End to isolation
But for Turkish Cypriots, outnumbered four to one by Greeks and earning only a third of Greek Cypriot wage levels, the rejection means they stay in international isolation.
The EU's eastern border will now be the so-called Green Line where 1200 UN peacekeepers police a mined strip of deserted land.
The 'Green Line' separates
Turkish and Greek Cyprus
EU Enlargement Commissioner Guenter Verheugen had told Germany's NDR radio shortly before the result he feared a Greek Cypriot "no". "Politically it would naturally be a very unwelcome situation".
Many Greek Cypriots say they cannot forget the Turkish invasion of the island in 1974 - which led to the present day de facto partition, writes Aljazeera.net's Jonathan Gorvett in Nicosia.
"I will vote no," said Eleni Stavrou, who runs a lace shop in the island's divided capital, Nicosia.
"Because if I voted yes it would be as if I was accepting what the Turkish troops did here - forcing us out of our homes at gunpoint."
"We've been educated since we were born to see the Turks as bad, as monsters," says Constantinos Arestides, another Nicosian. "Now, in the space of a few months, people are being asked to believe something entirely different."
Turkish Cypriot doubts
Turkish Cypriots too have their doubts, but in general see the Annan Plan as a good thing.
"It's time we ended this division," says Mehmet Ustaoglu, a mechanic from the Turkish side of Nicosia.
"My grandparents fought, my parents - it's time we stopped all this and reunited. Cyprus was once an island of peace, where Turks and Greeks, Christians and Muslims, lived side by side. But I think the Greek Cypriots are afraid of Turkey, that's the problem."
"After December you can forget any more chances for reunification," continues Christou. "If Turkey gets a date then, it won't bother about pressuring for a solution on Cyprus, while if it doesn't get a date, then it may even simply annexe the Turkish Cypriot part and have done with it"
Turkish Cypriot mechanic
While few expect a "double yes" vote, the extent of the 'no' vote on the Greek Cypriot side now seems crucial for the future course of events. "If its 60:40 against then there's still hope," says Jean Christou, chief reporter of the Cyprus Mail newspaper.
"Then it may still be possible for there to be another vote before December."
December is a vital month since that is when the EU is scheduled to decide if Turkey - Turkish Cyprus' big brother can get a date to begin EU membership negotiations.
"After December you can forget any more chances for reunification," continues Christou.
"If Turkey gets a date then, it won't bother about pressuring for a solution on Cyprus, while if it doesn't get a date, then it may even simply annex the Turkish Cypriot part and have done with it," he adds.
It's a comment that shows what is at stake in Saturday's referendum. While the two sides seem at their closest point ever to reuniting, failure may send both spinning in opposite directions again.