Both men are now poised to occupy two of the most important positions in President Barack Obama's Cabinet, leading observers on both sides of the Florida Straits to say the time could be ripe for a reboot in relations between the longtime Cold War enemies - despite major obstacles still in the way.
Kerry's confirmation hearing was held last Thursday, with Hagel's likely to begin next Thursday. In a day marked by platitudes and praise from his longtime colleagues, the Massachusetts Democrat up for top U.S. diplomat sidestepped two questions on Cuba without giving any hint of his opinion on bilateral relations.
Yet Kerry's record has showed some openness to relaxing the tough U.S. stance on Cuba.
"I think having a secretary of state and secretary of defense who understand and are willing to speak publicly that isolation is counterproductive is a very good start," said Tomas Bilbao, executive director of the nonpartisan Cuba Study Group, which advocates using engagement to spur democratic change. "I'm optimistic about the opportunity."
Carlos Alzugaray, an ex-Cuban ambassador to the European Union and the author of several studies about Cuba-US relations, said that if both men are confirmed, no Cabinet since the Carter administration would have such high-level voices in favor of rapprochement.
At the same time, the composition of Cuban-Americans in Florida is evolving, with younger voters less emotionally attached to the issue than their parents and grandparents. Exit polls showed 49 percent of Cuban-Americans in the state voted for Obama, roughly the same percentage as four years ago, an indication the group no longer plays the make-or-break role it once did in presidential politics.
The atmosphere is changing in Cuba as well.
Alzugaray noted that the island has taken many steps that would normally be welcomed by Washington such as freeing dozens of political prisoners, opening the economy to limited capitalism, hosting peace talks for war-torn Colombia and eliminating most restrictions on travel for its own citizens.
"Cuba is changing, and it is changing in the direction that the United States says Cuba must change," Alzugaray told The Associated Press in an interview in his Havana apartment.
The greatest obstacle to better ties is undoubtedly the continued imprisonment of U.S. contractor Alan Gross, who is serving a 15-year sentence for crimes against the state after he was caught setting up clandestine Internet networks as part of a U.S. Agency for International Development democracy-building program.
Havana has insisted the 63-year-old Gross will not be released unless Washington considers freeing five Cuban agents held in the United States. One is out on supervised release but was ordered to remain in the country, and the other four are still incarcerated.
Critics of engagement, including several prominent Cuban-American legislators, say none of the reforms Cuba has made brings the island closer to being a democratic state after 54 years of rule by brothers Fidel and Raul Castro.
Dissidents are still detained and harassed, they say, the Cuban news media is not free, elections are restricted to approved candidates and the Cuban parliament acts as little more than a rubber stamp for decisions made by the island's aging leaders.
Rep. Ileana Ros-Lehtinen, a Havana-born Florida Republican and staunch critic of the Castros, told the AP she was deeply concerned about both Cabinet nominees.
"I think both are bad for strengthening the U.S.-Cuba embargo," she said. "They would work for an appeasement policy. They would work to normalize relations. That is their philosophy. But they won't be able to achieve it."
Ros-Lehtinen said she hoped Kerry's likely replacement as chairman of the Senate Foreign Relations Committee, Cuban-American Democrat Bob Menendez of New Jersey, would block any attempt to take a softer line.
As committee chairman in 2011, Kerry held up millions of dollars in funding for the same program that Gross was involved in, out of concern that it was ill-conceived and a waste of money. He later cut a deal with Menendez to free up the money. At the hearing on Thursday, Kerry said that as secretary of state, he would support such programs worldwide, but did not mention Cuba.
Hagel, a former Republican senator from Nebraska, has termed the 50-year-old trade embargo an "outdated, unrealistic, irrelevant policy" and said the U.S. should engage with the island, just as it does with other communist countries such as Vietnam and China.
In his first term, Obama eliminated restrictions on the number of times Cuban-Americans can visit their relatives on the island, and the amount of money they can send back in remittances. He also has made it much easier for American travelers to get licenses to visit the island on cultural, educational and religious exchanges, though tourism is still barred.
Since 2009, the number of Americans traveling to Cuba has nearly doubled from 52,000 per year to 103,000 in 2012, according to statistics compiled by the firm the Havana Consulting Group. Trips by Cuban-Americans to visit their relatives rose from 335,000 to 476,000 a year during the same period. The surge puts the United States second only to Canada as the source of travelers to the island.
But just as American officials have met Cuban reforms with lukewarm indifference, Cuban leaders have dismissed Obama's overtures as window-dressing, saying he has in many ways strengthened the embargo by going after companies that do business with the island.
Cuban officials have been reluctant to talk about the Kerry and Hagel nominations for fear their words will be used by opponents. But a pro-government Web site, Cubasi, published an opinion piece Thursday detailing both men's past opposition to America's Cuba policy.
"Chuck Hagel has no problem with Cuba," wrote the author, well-known columnist Nicanor Leon Cotayo. "On the contrary, he has demonstrated common sense to do away with one of the White House's most anachronistic foreign policies."
Cotayo added that Obama has "real and legal options to maneuver and diminish tension in bilateral relations."
Others say they are not holding their breath for any change.
Alzugaray, the longtime Cuban diplomat, threw up his hands and shrugged when asked why he was not more optimistic that the stars would align for better relations this time around.
"That dog has bit me several times," he laughed. "I've often thought that now is the time, the possibilities are there, but always something has complicated things."
Associated Press writer Christine Armario in Miami contributed to this report.