29 марта 1916 года новым командиром «Императрицы Марии» стал известный нам капитан 1 ранга В.В. Трубецкой, отмеченный уже за подвиги в Великой войне орденом Св. Георгия 4-й степени и Георгиевским оружием. К.А. Порембский был назначен начальником бригады крейсеров и произведен в контр-адмиралы. Под его флагом уже с новым командиром линкор вместе с «Кагулом» и эсминцами 7 апреля вышел в шестидневное крейсерство к берегам Анатолии для прикрытия перевозки войск из Батума в Трапезунд.
24 апреля князь Трубецкой вновь вывел свой корабль с тремя эсминцами в море, пытаясь в очередной раз перехватить «Бреслау», но успеха не имел. Несколько ранее — утром 22 марта 1916 года, «племянник» встретился с маневренной группой «Императрицы Екатерины Великой», нобыл поздно обнаружен, так как находился в темной части горизонта. В ответ на затянувшийся со стороны русских процесс опознавания командир «Бреслау» капитан 2 ранта Кеттнер решил пошутить и просигналил по международному своду: «Счастливого пути». Дредноут немедленно открыл огонь и третьим залпом накрыл германский легкий крейсер, испытавший сотрясение, «как при минном взрыве». Полный ход, маневр на зигзаге и немного удачи позволили немцам оторваться от погони.
Редкий случай перехватить оба крейсера противника представился в июне 1916 года, когда немцы впервые направили их совместно в район Новороссийск — Сочи. Противник, о возможном выходе которого было известно заранее, 21 июня был обнаружен при обстреле им нашего побережья — в 480 милях от Босфора. Старые русские линкоры в это время находились в юго-восточной части моря, а адмирал А.А. Эбергардт с «Императрицей Екатериной Великой», двумя эсминцами и заградителями был в Севастополе. Вблизи Севастополя, т. е. всего в 270 милях от Босфора, держалась в море и «Императрица Мария» стремя эсминцами.
Оценив эту обстановку, начальник Морского штаба Верховного Главнокомандующего адмирал А.И. Русин в докладе Николаю II писал (исполнял доклад капитан 2 ранга А.Д. Бубнов): «Следовательно у Босфора своевременно могли бы быть сосредоточены: 2 линейных корабля, 5 миноносцев с 350 мин[ами] заграждения, две уже бывшие гам подводные лодки и даже минные заградители… В действительности командующий флотом вышел в море с линейным кораблем «Императрица Екатерина II» (так в тексте — Авт.), без мин заграждения на миноносцах, — только через сутки после появления “Гебена” у берегов Кавказа, в то время как последний уже подходил к Босфору».
Продержавшись в море два дня А.А. Эбергардт, не обнаружив противника, посчитал, что тот уже проскочил в пролив и вернулся в Севастополь, отозвав от Босфора и второй дредноут. На самом деле «Гебен» благополучно вошел в Босфор вечером 23 июня.
По мнению А.И. Русина, это была крупная неудача, и он доложил императору о необходимости смены командования Черноморским флотом, припомнив адмиралу А.А. Эбергардту в устном докладе все неудачи и потери флота с начала войны.
Новым командующим флотом был назначен сравнительно молодой и энергичный вице-адмирал А. В. Колчак, отличившийся к этому времени на Балтике и прибывший в Севастополь 8 июля 1916 года. Буквально сразу по прибытии он получил известие о выходе «Бреслау», который, как потом стало известно, направлялся с минами к Новороссийску.
Подняв флаг на «Императрице Марии», А.В. Колчак с «Кагулом» и пятью эсминцами 1-го и 2-го дивизионов 9 июля вышел в море. Первым обнаружил и атаковал противника эсминец «Счастливый», но на дистанции 80 каб неожиданно попал под огонь «Бреслау», стрелявшего из новых 150-мм орудий. Донесение «Счастливого» позволило в 14 ч 15 мин открыть огонь с дистанции 114 каб. Два первых залпа легли недолетами в 3,5–2,5 каб. «Бреслау» начал отход полным ходом на зигзаге с постановкой дымовой завесы и сбрасыванием мин за борт.