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 dispersionless mode, characterized by a dynamical spin ice structure factor. Unexpectedly, this mode is found to survive above T_{N}≈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_{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.