We report on a search for heavy neutrinos in B-meson decays. The results are obtained using a data sample that contains 772x10^6 BB-bar pairs collected at the Upsilon(4S) resonance with the Belle detector at the KEKB asymmetric-energy e+e- collider. No signal is observed and upper limits are set on mixing of heavy neutrinos with left-handed neutrinos of the Standard Model in the mass range 0.5 - 5.0 GeV/c^2.