Infinite projected entangled pair states simulations of the
S=1 bilinear-biquadratic Heisenberg model on the square lattice reveal an emergent Haldane phase in between the previously predicted antiferromagnetic and three-sublattice ${120}^{\ensuremath{\circ}}$ magnetically ordered phases. This intermediate phase preserves SU(2) spin and translational symmetry but breaks lattice rotational symmetry, and it can be adiabatically connected to the Haldane phase of decoupled
S=1 chains. Our results contradict previous studies which found a direct transition between the two magnetically ordered states.