U.S. Assistant Secretary of State Victoria Nuland addresses a news conference at the U.S. embassy in Kiev Thursday. Reuters

The U.S. strongly suspects Russian involvement in the leak of a recording of a top diplomat referring profanely to America's allies, comments that lay bare growing frustrations between the U.S. and Europe as they try to forge a solution to the political crisis in Ukraine.

U.S. officials didn't dispute the authenticity of a recording in which U.S. Assistant Secretary of State Victoria Nuland, speaking to another U.S. diplomat last month, is heard apparently voicing her exasperation over political differences with European Union officials by saying, "f— the EU."

Ms. Nuland, the top U.S. diplomat for Europe, has apologized to her EU counterparts for the "reported comments," State Department spokeswoman Jennifer Psaki said Thursday.

An EU spokeswoman declined to comment on the recording, saying only that the EU is "engaged in helping the people of Ukraine through" the current political crisis.

The U.S. officials said an aide in the office of Russia's deputy prime minister was the first to send a Twitter TWTR -1.54% Twitter Inc. U.S.: NYSE $54.91 -0.86 -1.54% Feb. 28, 2014 4:01 pm Volume (Delayed 15m) : 8.10M AFTER HOURS $54.71 -0.20 -0.36% Feb. 28, 2014 7:59 pm Volume (Delayed 15m): 51,856 P/E Ratio N/A Market Cap $30.49 Billion Dividend Yield N/A Rev. per Employee $332,445 02/28/14 Live Polling on Twitter to Hav... 02/28/14 What Your CEO Is Reading: Sili... 02/27/14 Dark Forecast for Twitter's U.... More quote details and news » message about the recorded phone call between Ms. Nuland and Geoffrey Pyatt, the U.S. ambassador to Ukraine.

Senior U.S. officials say they suspect Russia intercepted the phone conversation but don't know for certain.

White House press secretary Jay Carney said that because the recording was "first noted and tweeted out by the Russian government, I think it says something about Russia's role."

Ms. Psaki called it "a new low in Russian tradecraft."

The U.S. has for months been accused by some of its allies of illicit surveillance and spying, charges related to the National Security Agency's collection of data concerning phone calls and emails.

However, the interception of a U.S. diplomatic phone call, if shown to be orchestrated by Russia, would highlight a frequent U.S. counterargument: that other countries engage in electronic surveillance, but don't disclose it.

The recordings, posted by an anonymous user on YouTube, come as Moscow has been stepping up its rhetoric against Western influence in Ukraine, accusing the U.S. and EU of orchestrating street protests and encouraging a coup against President Viktor Yanukovych.

In an interview published Thursday in the Kommersant-Ukraine newspaper, a senior Kremlin adviser, Sergei Glazyev, accused the West of financing and arming the political opposition and street protesters. He indicated that Russia could intervene to protect Ukraine's security, as "interference" by the U.S. breached a 1994 memorandum signed by Russia and the U.S. guaranteeing Ukraine's territorial integrity.

In Moscow, Russian Deputy Prime Minister Dmitry Rogozin, whose aide on Twitter drew early attention to the recordings on YouTube, tweeted, "Well, naturally, the Russians are guilty of everything, of 'being the first to publish the YouTube link on Twitter.'"

The U.S. and Europe have attempted to present a united front in helping Ukraine's westward-leaning opposition climb down from a testy standoff with Mr. Yanukovych.

His opponents continue to man barricades in the center of the Ukrainian capital, protesting his abrupt decision last year to scuttle a planned cooperation agreement with the EU and instead accept a $15 billion financial package from the Kremlin.

The U.S. has taken a hard line toward Mr. Yanukovych's government, and has threatened sanctions on top officials who authorize the use of violence against protesters—a move the EU has so far refused to make.

The U.S. and EU also are assembling an aid package to encourage the Ukrainian president and opposition to form a transitional government to end the crisis.

In one of the audio recordings, Ms. Nuland and Mr. Pyatt discuss how to coax opposition leaders into forming a new coalition government with Mr. Yanukovych as a way out of the crisis.

The conversation apparently took place after Mr. Yanukovych dismissed his prime minister and cabinet last month and offered cabinet positions to his opponents. They eventually refused the posts, which they said carried little power under Ukraine's constitution.

In the recording, the diplomats agreed that Arseny Yatsenyuk, a former foreign minister of Ukraine, had a good grasp of economics and management, and could function well in the new government.

But they agreed that Vitali Klitschko, a former heavyweight boxer, was too inexperienced. "Just let him stay out and do his political homework and stuff," Mr. Pyatt said.

The diplomats said that a major challenge was to hold moderate politicians together, and not to let radicals in the protest movement upset any agreement. They also worried about Russia, which they said was working behind the scenes to undercut any deal.

Ms. Nuland said she had gotten the U.N. to agree send an official to Ukraine to "help glue this thing and to have the U.N. glue it and, you know, f— the EU."

"Exactly," responded Mr. Pyatt. "And I think we've got to do something to make it stick together."

Otherwise, he said, Moscow would work behind the scenes "to try to torpedo it."

—Colleen McCain Nelson, James Marson and Laurence Norman contributed to this article.

Write to Alan Cullison at alan.cullison@wsj.com and Adam Entous at adam.entous@wsj.com