  Many clever routes to Majorana fermions have been discovered by exploiting
the interplay between superconductivity and band topology in metals and
insulators. However, realizations in semimetals remain less explored. We ask,
``under what conditions do superconductor vortices in time-reversal symmetric
Weyl semimetals -- three-dimensional semimetals with only time-reversal
symmetry -- trap Majorana fermions on the surface?'' If each constant-$k_{z}$
plane, where $z$ is the vortex axis, contains equal numbers of Weyl nodes of
each chirality, we predict a generically gapped vortex and derive a topological
invariant $\nu=\pm1$ in terms of the Fermi arc structure that signals the
presence or absence of surface Majorana fermions. In contrast, if certain
constant-$k_{z}$ planes contain a net chirality of Weyl nodes, the vortex is
gapless. We analytically calculate $\nu$ within a perturbative scheme and
provide numerical support with a lattice model. The criteria survive the
presence of other bulk and surface bands and yield phase transitions between
trivial, gapless and topological vortices upon tilting the vortex. We propose
Li(Fe$_{0.91}$Co$_{0.09}$)As and Fe$_{1+y}$Se$_{0.45}$Te$_{0.55}$ with broken
inversion symmetry as candidates for realizing our proposals.
