The formal signing comes six days after the two countries agreed to a deal that will see 10 US interceptor missiles placed by 2011-2013 just 18km from Russia's westernmost frontier.
"The negotiations were very tough but friendly," Donald Tusk, Poland's prime mnister said to Rice in English, after the signing.
"We have achieved our main goals, which means that our country and the United States will be more secure."
The deal has sparked threats from Russia that Poland is making itself vulnerable to attack - even a nuclear one.
Along with Russia's rhetoric, the agreement has further strained Moscow's ties with the West in the wake of its fighting with Georgia, a US ally.
'Incendiary comments'
Neave Barker, reporting for Al Jazeera from Moscow, said: "The first indication that this [signing] was going to happen took place a few days ago - mid conflict [between Russia and Georgia] I might add - where Poland indicated it was willing to allow the US to station its missile defence shield on its territory."
Russia then took this indication to mean that the intended target of the missile defence shield was not, as the US claimed, rogue states - the likes of Iran - but Russia, said Barker.
"That's the main concern here, and what we have been seeing over the past few days is Russia acting accordingly to beef up its own defences as well," he added.
"We have heard some incendiary comments from the ministry of defence here that Poland would now be perhaps a new target for Russian missiles."
Lech Kaczynski, Poland's president, said on Wednesday that the signing ceremony would be "an important day in our history".
The deal "strengthens Poland's position in the world", Kaczynski said in a televised address on Tuesday evening.
The country has in recent years joined the EU and is a member of Nato.
Philip Coyle, a senior adviser with the Centre for Defence Information in Washington DC, said the Bush administration has been trying for about 18 months to reach this deal, but the timing has turned out to be "most unfortunate from a Russian point of view".
"The tragedy in all of this confrontation with Russia is that the system that's proposed for Poland and the Czech Republic is a scarecrow," he told Al Jazeera.
"It's not something that Europe can rely on, it is not dependable. If Iran had missiles that could reach central Europe, which they don’t yet, this system couldn't be relied on to defend against them anyway."
'Sword-rattling'
The "commotion and sword-rattling with Russia is for nothing", Coyle said.
"Some of this may be just a threat, but Russia has shown in just the past week or so it has a formidable military force, so if I were Poland or the Czech Republic, I would be more worried about Russia than I would be about Iran or North Korea."
The US says the missile defence system is aimed at protecting it and Europe from future attacks from states such as Iran.
It rejects Moscow's insistence that it is a threat to Russia.
For Poles, it has a further dimension at a time when Russia's actions in Georgia have generated alarm throughout Eastern Europe.
They see it as offering a form of protection beyond that of Nato in light of a resurgent Russia to the east.
The two countries spent a year and a half negotiating, and talks recently had stalled on Poland's demands that the US bolster Polish security with Patriot missiles in exchange for hosting the missile defence base.
Washington agreed to do so last week, as Poland invoked the Georgia conflict to strengthen its case.
Short-range missiles
The Patriots are meant to protect Poland from short-range missiles from neighbours - such as Russia.
Kaczynski stressed that the missile defence shield was purely a defensive system and not a threat to any nation.
"For that reason, no one who has good intentions toward us and toward the Western world should be afraid of it," he said.
Poles have been shaken by Russian threats against their nation in punishment for accepting the US site.
A day after Warsaw and Washington reached agreement on the deal last week, a leading Russian general made his country's strongest warning to date against the system.
"Poland, by deploying [the system] is exposing itself to a strike - 100 per cent," General Anatoly Nogovitsyn was reported as saying on Friday by the Interfax news agency.