We consider the conversions of active to sterile Majorana neutrinos νa and νs, due to neutrino transition magnetic moments in the presence of random magnetic fields (r.m.f.) generated at the electroweak phase transition. From a simple Schr\'{o}dinger-type evolution equation, we derive a stringent constraint on the corresponding transition magnetic moments and display it as a function of the domain size and field geometry. For typical parameter choices one gets limits much stronger than usually derived from stellar energy loss considerations. These bounds are consistent with the hypothesis of seeding of galactic magnetic fields by primordial fields surviving past the re-combination epoch. We also obtain a bound on active-sterile neutrino transition magnetic moments from supernova energy loss arguments. For r.m.f. strengths in the range 107 to 1012 Gauss we obtain limits varying from $\mu_{as}^{\nu} \lsim 10^{-13}\mu_B$ to $\mu_{as}^{\nu} \lsim 10^{-18}\mu_B$, again much stronger than in the case without magnetic fields.