  We investigate the temperature dependence of the spin dynamics in the
pyrochlore magnet Nd$_2$Zr$_2$O$_7$ by neutron scattering experiments. At low
temperature, this material undergoes a transition towards an "all in - all out"
antiferromagnetic phase and the spin dynamics encompass a dispersion-less mode,
characterized by a dynamical spin ice structure factor. Unexpectedly, this mode
is found to survive above $T_{\rm N} \approx 300$ mK. Concomitantly, elastic
correlations of the spin ice type develop. These are the signatures of a
peculiar correlated paramagnetic phase which can be considered as a new example
of Coulomb phase. Our observations near $T_{\rm N}$ do not reproduce the
signatures expected for a Higgs transition, but show reminiscent features of
the "all in - all out" order superimposed on a Coulomb phase.
