En junio de 2006, Teodosia saltó a las noticias en relación con las protestas contra la OTAN de 2006.