30 sierpnia 1481 roku w Wilnie pod zarzutem próby królobójstwa ścięto Michała Olelkowicza i Iwana Holszańskiego. Fedorowi Bielskiemu udało się zbiec do Wielkiego Księstwa Moskiewskiego - w Wielkim Księstwie Litewskim pozostawił swoją dzień wcześniej poślubioną żonę, Annę (wraz z księciem do Moskwy uciekł również Tichon Łuchowski, późniejszy święty prawosławny).
Ucieczka do Wielkiego Księstwa Moskiewskiego mały|Fedor Bielski otrzymuje miasta od Iwana III Srogiego Wielki książę moskiewski dobrze przyjął i kniazia i darował mu Diemiansk i Mariowo. Poza tym utrzymał udzielne księstwo łuchskie wraz z m.in. Kineszmą. W 1485 roku towarzyszył wielkiemu księciu w pochodzie na Twer. W 1493 roku, za domniemaną chęć ucieczki na Litwę i udział w spisku księcia Łukomskiego, został zesłany do Galicza. Szybko jednak wrócił do łask wielkiego księcia. W 1499 roku dowodził armią wysłaną na pomoc chanowi kazańskiemu Abdullatifowi. W 1502 roku brał udział w wojnie przeciwko Litwie, w tym także w nieudanym oblężeniu Smoleńska. W 1506 roku był jednym z dowódców wyprawy na Kazań. mały|Ślub Fedora Bielskiego z księżniczką Anną Riazańską Sprawa sprowadzenia pierwszej żony księcia Anny Kobryńskiej stanowiła jeden z istotnych punktów dyplomacji pomiędzy Wielkim Księstwem Moskiewskim a Wielkim Księstwem Litewskim.