Let X be a normal variety of positive dimension over a finite field of characteristic \(p>0\) and let \(\mathcal {C}\) be either a locally constant constructible Weil \(\overline{\mathbb {Q}}_\ell \) -sheaf, a locally constant constructible quasi-tame \(\overline{\mathbb {Q}}_\mathfrak {u}\) -sheaf or an overconvergent \(\overline{\mathbb {Q}}_p\) -F-isocrystal on X. We prove the following Tannakian Cebotarev density theorem: let S be a set of closed points of X of upper Dirichlet density 1 (resp. \(>0\) ) and \(\Phi \) the union of conjugacy classes of Frobenius elements corresponding to S in the Tannakian group \(G(\mathcal {C})\) of \(\mathcal {C}\) . Then \(\Phi \) is Zariski-dense in (resp. the Zariski-closure of \(\Phi \) contains at least one connected component of) \(G(\mathcal {C})\) . We use the theory of companions and its by-product, the existence of a weight filtration, to reduce the general statement to the case of locally constant constructible étale \(\overline{\mathbb {Q}}_\ell \) -sheaves, where the assertion is an easy consequence of the (classical) Cebotarev density theorem. The reduction step relies on group-theoretic arguments which might be of independent interest. When X is smooth, our strategy can be adapted to reduce the Tannakian Cebotarev density theorem for convergent \(\overline{\mathbb {Q}}_p\) -F-isocrystals satisfying a weak form of the parabolicity conjecture of Crew (resp. for overconvergent \(\overline{\mathbb {Q}}_p\) -F-isocrystals) to the case of direct sums of isoclinic \(\overline{\mathbb {Q}}_p\) -F-isocrystals, which is due to Hartl and Pál. Since the parabolicity conjecture is known for convergent \(\overline{\mathbb {Q}}_p\) -F-isocrystals admitting an overconvergent extension by recent work of D’Addezio and is straightforward for convergent \(\overline{\mathbb {Q}}_p\) -F-isocrystals admitting a slope filtration, this in particular proves unconditionally the Tannakian Cebotarev density theorem in those two cases. Let us point out that this variant of our strategy for convergent (resp. overconvergent) \(\overline{\mathbb {Q}}_p\) -F-isocrystals is purely p-adic and “elementary” in the sense that it does not resort to automorphic techniques via the companion conjecture (nor to the “à la Weil II” formalism of Frobenius weights).