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 ν=±1 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 ν 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.