About 60 Russian troops in six helicopters and three armored vehicles reportedly crossed into Ukraine's Kherson region and were in the town of Strilkove, on a strip of land just northeast of Crimea.
The State Border Guard Service of Ukraine said the Russian troops were on the ground and the Ukrainian guards had taken defensive positions.
The region is key to neighboring Crimea, because it gets electricity, freshwater and natural gas from there.
The Russians said they were in Kherson to prevent a possible terrorist attack on oil assets in the area, according to the Ukrainian border guards.
Ukraine's foreign ministry termed the move a "military invasion" and called on Russia to withdraw its forces.
Also Saturday, Russia wielded it's veto power as a permanent member of the U.N. Security Council against a U.S. draft resolution that declared Sunday's Crimea referendum invalid.
Thirteen of the 15 Security Council members backed the resolution, while China abstained.
"The reason only one country voted 'no' today is that the world believes that international borders are more than mere suggestions," said U.S. Ambassador Samantha Power after the vote.
Russian Ambassador Vitaly Churkin argued that Crimean citizens had a right to self-determination.
What happens next in Crimea?
Blue white and red Russian flags dominate the streets of the coastal Crimean town of Sevastopol, where concerts on the main square have been celebrating the return to the "motherland" this past week.
"Everybody believes the results are already rigged," said CNN iReporter Maia Mikhaluk from Kiev.
"People are concerned what is going to happen after the referendum," she said.
"People are concerned that the Russian army will use force, guns to push (the) Ukrainian army from Crimea."
The referendum will present Crimean residents with the choice of whether to secede from Ukraine and join Russia or effectively become independent.
Ukraine's acting foreign minister, Andrii Deshchytsia, repeated Saturday the interim government's position that the referendum is illegitimate and will not be recognized by Kiev or the international community.
Ukraine is engaged in a "diplomatic war" with Russia, he said, but is looking for a peaceful resolution to the crisis in Crimea.
It will not respond to Russian "provocations," he said.
Russia -- which the West and Ukraine insist has the majority ethnic Russian Crimean peninsula under its effective military control -- has come under concerted international pressure to halt its activities there and talk to the interim government in Kiev.
But, so far, it has refused to budge.
Moscow has repeatedly denied direct involvement in Crimea, saying that the well-armed men in uniforms without identifying insignia are not Russian troops.
Protests for both sides
In the eastern Ukraine city of Donetsk, thousands of pro-Russia demonstrators rallied beneath a towering statue of Soviet revolutionary Vladimir Lenin in the city's main square.
They waved Russian flags and red flags emblazoned with the iconic image of Argentinian Marxist revolutionary Che Guevara.
There was not a single Ukraine flag to be seen, according to a CNN team on the ground.
"They are frightened," said local journalist Denis Kazansky of pro-Ukraine protesters.
"They will not come out and demonstrate."
A man was fatally stabbed and at least 10 others were injured in clashes in Donetsk on Thursday.
Russia blamed "right-wing radical groups" for the violence, while Ukrainian authorities suggested it was linked to Russian citizens who want to escalate tensions in Ukraine.
Many people living in Ukraine's eastern region, along the Ukraine-Russia border, identify more with Russia than with Ukraine.
Saturday, protesters also took to the streets in the Russian capital, Moscow.
State news agency Itar-Tass, citing Moscow police, said some 15,000 turned out for a rally in support of the referendum in Crimea, while about 3,000 marched in protest against attempts to reunite Crimea with Russia.
The Black Sea peninsula was part of Russia until Soviet leader Nikita Khrushchev gave it to Ukraine in 1954.
Ukraine was then part of the Soviet Union.
But Russia maintains its Black Sea Fleet in Crimea.
Despite U.S. warnings of "costs" for Russia if the vote goes ahead, Moscow has refused to budge on the crisis.
Lengthy talks between U.S. Secretary of State John Kerry and his Russian counterpart, Sergey Lavrov, in London on Friday resulted in little more than an acknowledgment of the gap between them.
As Lavrov said, "We don't have a common vision."
Meanwhile, thousands of Russian troops continued a large-scale military drill near the Ukraine border.
On the same day, armored trucks toting long-range guns and other military equipment rumbled through northern Crimea.
At least one of the vehicles seen by CNN had Russian license plates.
Already, eight Ukrainian military units in Crimea have been taken over, 22 others are blocked, and 49 of 56 border patrol stations are in similar straits, Ukraine's foreign ministry said.
Kiev's new Western-leaning government, which came to power following the ouster of President Viktor Yanukovych, has insisted that Ukraine's territorial integrity, including Crimea, must be respected.
Moscow has insisted it has the right to protect ethnic Russians in Ukraine, who it claims are threatened by radical nationalists and "fascists."
Estonia's defense minister, Urmas Reinsalu, said Friday that Ukraine is on the verge of a full-scale military conflict unless Russian President Vladimir Putin's hand is forced.
"It is clear that we are at a crossroads," U.N. Secretary-General Ban Ki-moon said.
"If positions continue to harden and rhetoric continues to sharpen, there is great risk of a dangerous downward spiral."
Russia so far has refused to engage in direct talks with Ukraine's new leaders, although Lavrov said some communication continues with the interim government in Kiev.
Moscow has also denied any direct involvement in Crimea, saying what's happening in the Black Sea peninsula is an internal matter.
Russia has a major naval base in the Crimean port city of Sevastopol, and thousands of its troops are stationed there.
European nations and the United States have announced some targeted punishments against Russia in addition to offers of billions in aid to Ukraine's fledgling government.
Russia has seen steep declines in its stock market and the value of the ruble in recent days.
The State Department has cautioned Americans about traveling to Russia given "the possibility of violence or anti-U.S. actions directed against U.S. citizens or U.S. interests."
Kerry warned Friday that the "consequences" will be far more stringent should Putin sign off on the "back-door annexation" of Crimea.
Lawmakers in Moscow are due to vote next Friday on accepting Crimea into the Russian Federation should there be a "yes" vote in the referendum.
At the same time, Kerry opened the door for less strident measures should Russia opt not to take in Crimea -- whatever the referendum says -- and instead go along with greater autonomy.