Georgian authorities and security experts, however, called the accusations "paranoid" and "hard to believe."
Russia's National Anti-Terrorist Committee said the FSB, the successor agency to the KGB, had discovered ten caches of weapons and ammunition on May 4 and May 5 in Georgia's breakaway republic of Abkhazia, which lies just miles from Sochi.
The arms seized included portable surface-to-air missiles, grenade launchers, flame throwers, grenades, rifles, explosives and maps, the security service said.
Authorities said the terrorists were planning to smuggle the explosives and arms into Sochi "between 2012 and 2014 to use them during the preparations and during the games." They did not elaborate on how they came to this conclusion.
Sochi is less than dozen miles away from Russia's border with Abkhazia, a tiny province on the Black Sea that declared independence from Georgia in 2008. Few countries other than Russia have supported its independence and it remains roiled by political unrest.
The FSB said it suspects the mastermind behind the plans targeting Sochi is Chechen rebel leader Doku Umarov, whom it alleges has close ties to Georgia's secret service. The secret service said Umarov had co-ordinated the delivery of the weapons and ammunition to Abkhazia and arranged caches for them.
Umarov has previously claimed responsibility for the 2011 deadly bombing in a Moscow airport that killed 35 people. The ailing Chechen separatist is widely seen as the nominal leader of fractured groups of Islamists and separatists in Russia's volatile North Caucasus region.
Georgia and Russia had a brief but intense war in 2008 and are still very distrustful of each other. Georgia has accused Russia of sending spies and supporting a failed coup to topple pro-Western President Mikhail Saakashvili and has urged the world to boycott the Sochi Games.
On Thursday, Shota Khizanishvili, the chief of staff at Georgia's Interior Ministry, denied any links between Georgia and Umarov.
"I can only say that the National Anti-Terrorist Committee is staffed with people with peculiar fantasies," Khizanishvili told The Associated Press. "They're always trying to accuse Georgia and its secret services of everything in any situation and without any grounds. This is a sign of severe paranoia."
A regional security expert agreed that the Russian accusations were "hard to believe."
"(Georgian authorities) can hardly side with separatists and organize diversions," Akhmet Yarlykapov of the Moscow-based Ethnology and Anthropology Institute told the AP.
Sochi's selection as the host of the 2014 Winter Games had sparked fears of possible terrorist activity, although no attacks have occurred so far.
The city is located in the same area as Russia's North Caucasus, which is plagued with near-daily violence linked to an Islamist insurgency that spread from the province of Chechnya to neighbouring areas in the late 1990s.
The International Olympic Committee would not comment on the specific security case at Sochi but said in a statement that "security is a top priority for the IOC.
"Security at the games is the responsibility of the local authorities, and we have no doubt that the Russians will be up to the task," the statement said.
Misha Dzhindzhikhashvili from Tbilisi, Georgia, and sports writer Stephen Wilson in London contributed to this report.