We prove that all eigenstates of many-body localized symmetry protected topological systems with time reversal symmetry have four-fold degenerate entanglement spectra in the thermodynamic limit. To that end, we employ unitary quantum circuits where the number of sites the gates act on grows linearly with the system size. We find that the corresponding matrix product operator representation has similar local symmetries as matrix product ground states of symmetry protected topological phases. Those local symmetries give rise to a $mathbb{Z}_2$ topological index, which is robust against arbitrary perturbations so long as they do not break time reversal symmetry or drive the system out of the fully many-body localized phase.