Anti-NATO motivated protests (including 1 riot) took place in the Ukrainian port city of Feodosiya late May/early June 2006, partially disrupting a joint Ukrainian-U.S. military exercise; which was canceled 20 July 2006.
The military Ukraine-NATO Partnership for Peace military exercise Sea Breeze 2006 exercise (in Crimea) was scheduled to take place in Ukraine starting 17 July 2006. Its aim was to "simulate the defence of a peninsula caught between a totalitarian state and a democratic one." "Sea Breeze" manoeuvres had been held annually since 1997. Another British-Ukrainian war-game called "Tight Knot" was scheduled to start on 14 June 2006 (near Mykolaiv).
On 4 June Ukrainian President Viktor Yushchenko signed a decree on preparations of the two war-games. The approval for the exercises by the Verkhovna Rada (Ukraine's parliament) was still pending early June 2006 because after the parliamentary election of March 2006 it resumed its work on 7 June 2006. In February 2006 the Verkhovna Rada elected before the 2006 election rejected a presidential bill on allowing foreign troops to take part in the maneuvers planned for 2006. The Verkhovna Rada was due to vote on the same bill on 7 June 2006, but decided to adjourn until 14 June.
On 6 June 2006 the Crimean legislature declared Crimea a "NATO-free territory" despite lacking any legal jurisdiction over such issues. The parliament actually has no right of legislative initiative.
on 27 May 2006 the United States (U.S.) cargo ship "Advantage" anchored in Feodosiya, bringing what Ukrainian Defense Minister Anatoliy Hrytsenko described as U.S. "technical aid." (Unarmed) seamen offloaded construction materials to build barracks for Ukrainian sailors at a training range near the town of Stary Krym, not far from Feodosiya. Two days later, Feodosiya 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, displaying anti-NATO slogans written in Russian and blocking U.S. cargo from getting to its destination.