We prove that a finite group $G$ has a normal Sylow $p$-subgroup $P$ if, and only if, every irreducible character of $G$ appearing in the permutation character $(1P)G$ with multiplicity coprime to $p$ has degree coprime to $p$. This confirms a prediction by Malle and Navarro from 2012. Our proof of the above result depends on a reduction to simple groups and ultimately on a combinatorial analysis of the properties of Sylow branching coefficients for symmetric groups.