W 1886 r. rozpoczął podróż po Europie. Wiosną tego roku ubiegał się w Londynie o rękę Marii Teck, jednak został odrzucony. W ciągu kolejnych lat bezskutecznie poszukiwał małżonki, odrzucany kolejno przez Irenę z Hesji-Darmstadt i Ludwikę Koburg. Próbował też szczęścia wśród osiadłej we Francji polskiej szlachty, jednak propozycja ożenku z Magdaleną Collana-Walewską (1869–1955), wnuczką Aleksandra, spotkała się z ostrym sprzeciwem matki wielkiego księcia. W 1888 r. powrócił do Rosji, gdzie wikłał się w burzliwe romanse. Kolejny projekt małżeństwa z Jekatieriną Ignatiewą (1869–1914), córką Nikołaja, został zaaprobowany przez cara Aleksandra III. Jednak Olga Fiodorowna nie wyraziła zgody również na ten związek i wysłała syna w podróż za granicę.
Podczas pobytu w Nicei w 1890 r. Michał Michajłowicz poznał Zofię von Merenberg, która pomimo że była hrabianką i wnuczką Aleksandra Puszkina, również mogła być uznana przez cara za osobę nierówną stanem społecznym. Dlatego nie czekając na odpowiednie zezwolenia dworu para wzięła ślub już 26 lutego 1891 w San Remo (związek morganatyczny). Samowola wielkiego księcia wywołała skandal na dworze carskim. Został on zdegradowany w służbie wojskowej i pozbawiony stanowiska adiutanta dworu.