Anti-NATO protests (including one riot) took place in the Ukrainian port city of Feodosia from late May to early June 2006, partially disrupting a joint Ukrainian-U.S. military exercise, which was canceled 20 July 2006.

[3][5] On 27 May 2006, the United States (U.S.) cargo ship Advantage anchored in Feodosia, bringing what Ukrainian Defense Minister Anatoliy Hrytsenko described as U.S. "technical aid.

"[4] Unarmed[3] seamen offloaded construction materials to build barracks for Ukrainian sailors at a training range near the town of Stary Krym, not far from Feodosia.

[4] Two days later, Feodosia residents, mobilized by local chapters of the Party of Regions, the Nataliya Vitrenko Bloc, and the Russian Community of Crimea, began to picket the port,[4] displaying anti-NATO slogans written in Russian and blocking U.S. cargo from getting to its destination.

[6] On 20 July 2006 the United States cancelled Sea Breeze, "due to the situation in the Middle East".