Константин Константинович решается при посредничестве великого князя Сергея Александровича просить Александра III уволить его из флота, о чем и написал другу детства. В ожидании решения он 17 декабря 1881 года отправляется в Каир и Александрию. Не успев вдоволь налюбоваться пирамидами и арабскими базарами, он подхватил воспаление легких и на фрегате «Забияка» был перевезен в Палермо, где медленно стал выздоравливать.
Оправившись полностью от болезни к середине марта 1882 года, великий князь вернулся в Афины. К этому времени Александр III уже удовлетворил его просьбу и уволил из флота, не согласовав свое решение, как требовал обычай в августейшем семействе, с отцом Константина Константиновича.
Константин Николаевич, узнав из третьих рук, что сын вышел из повиновения и государь поддержал его, был вне себя от грусти и даже временами впадал в ярость. Он искренно скорбел о неосуществленной мечте создать потомство Константиновичей, служащих русскому флоту.
Путешествуя по Европе, Константин Николаевич просит сына встретиться в Вене. Константин Константинович едет, готовый дать бой, но не уступить. Когда же увидел отца, уже не столь грозного, как раньше («у него слезы были на глазах»), и услышал не гневную отповедь, а жалобу, «что теперь, когда он и так уже много сряду имел неприятностей, эта рана останется неизлечимой до конца его жизни», ему стало жаль отца. Но еще больше себя, когда подумал, что всю жизнь придется связать с морем, которым хорошо любоваться с берега, и только. Константин Константинович впервые оказался упрям, и отцу пришлось смириться с неизбежным. Сын свободно вздохнул: «Теперь гора с плеч свалилась» (7 мая 1882 г.).
Свобода обретена. Оставалось подыскать себе по вкусу и высокому положению невесту. Романовы были в родстве со многими немецкими семействами королевской крови, и не составляло труда, кочуя по Германии от одного родственника к другому, приглядеться к молодым принцессам.
В Карслуте кузина Маруся познакомила Константина Константиновича со своей дочерью Мари. Он присматривается к ней, как к породистой лошади.
«Первое впечатление было неопределенное: носик, может быть слишком вздернутый, и волосы, слишком высоко зачесанные назад, хороший цвет лица, глаза незадумчивые, почти детские, движения свободные, не некрасивые. Выражение лица своей беспечностью и детской развязанностъю не подходили к фигуре уже взрослой девушки. Я внутренне задавал себе вопрос: «Эта или нет?» Но ответа внутри никакого не слышалось»
