In Sevastopol, the Russian leader celebrated Victory Day, marking the defeat of Nazi Germany in 1945, and watched a parade of Russian navy ships and a flyby of Russian aircraft.
He thanked the armed services for their role in World War II.
"The example of Sevastopol shows the world that in places where people are ready to fight for their freedom, the enemy will never conquer," Putin told the adoring crowds in the port city that is home to the Russian Black Sea naval fleet.
He added that "2014 will make it into the history of Sevastopol and the history of our country, because this is the year that the people of Crimea decided firmly to be with Russia, thus proving their loyalty to historical memory and the memory of our predecessor."
"We have lots of work in front of us, but we will overcome all the difficulties, because we are together, and that means we have become stronger," he said, according to The Washington Post.
Inspecting warships from a naval launch in the harbor, he shouted into a microphone to each vessel, "Hello, Comrades!" and the men, dressed in navy blue dress uniforms, shouted back a greeting, followed by a rousing "Hurrah!" The New York Times reports.
Earlier, Putin joined thousands in Moscow's Red Square Friday for a similar celebration that featured an unusually large display of military might.
NATO's Secretary General Anders Fogh Rasmussen, who is visiting the former Soviet republic of Estonia, said Friday that Putin's visit to Crimea "is inappropriate."
Meanwhile, major fighting erupted in the Ukrainian port city of Mairupol as Ukrainian troops crack down on pro-Russian separates.
Ukraine's Interior Minister Arsen Avakov said in a statement that 20 "terrorists" and one police officer were killed in fighting that erupted when 60 gunmen tried to capture the police station in this city of around 500,000 people and were rebuffed by police and the military.
In Moscow, the Victory Day celebration blended comfortably with a surge of patriotic feeling among many Russians over the annexation of Crimea and a sense of restoring Russian pride.
"It is a holiday when an overwhelming force of patriotism triumphs, when all of us feel particularly acutely what it means to be loyal to the Motherland and how important it is to defend its interests," Putin said, addressing crowds on Red Square, as thousands of troops filed past him to the tunes of patriotic songs.
Putin made no reference to the situation in Ukraine when he opened Friday's parade, focusing instead on the historic importance of the victory over fascism, but this year's parade was larger than it has been in recent years.
Some 150 military vehicles and about 70 combat aircraft took part in the show, an event that gives Moscow the opportunity to show off its military hardware to the world while remembering the victims of World War II and those who defeated Nazi Germany.
The BBC reported that the parade lasted 59 minutes compared to its usual running time of 45 minutes and that there were 50 more military vehicles involved in the procession this year over last.
"The iron will of the Soviet people, their fearlessness and stamina saved Europe from slavery. It was our country which chased the Nazis to their lair, achieved their full and final destruction, won at the cost of millions of victims and terrible hardships," Putin said.
"We will always guard this sacred and unfading truth and will not allow the betrayal and obliteration of heroes, of all who, not caring about themselves, preserved peace on the planet."
In a separate development in Ukraine, a fire briefly broke out in the vicinity of a main broadcasting tower in the Ukrainian capital of Kiev on Friday, disrupting some television services.
Kiev's mayor's office said the fire appears to have been the result of a shorting circuit rather than a deliberate act of sabotage, the Interfax news agency reported.
That was disputed by Ukraine's security services, who said the fire was an act of sabotage.
Activists in the Russian-speaking east of Ukraine are set to defy this weekend a call by Putin to delay planned referendums on autonomy.
Source: Associated Press