Pulse Doppler radars suffer from range-Doppler ambiguity that translates into a trade-off between maximal unambiguous range and velocity. Several techniques, like the multiple PRFs (MPRF) method, have been proposed to mitigate this problem. The drawback of the MPRF method is that the received samples are not processed jointly, decreasing signal to noise ratio (SNR). To overcome the drawbacks of MPRF, we employ a random pulse phase coding approach to increase the unambiguous range region while preserving the unambiguous Doppler region. Our method encodes each pulse with a random phase, varying from pulse to pulse, and then processes the received samples jointly to resolve the range ambiguity. This technique increases the SNR through joint processing without the parameter matching procedures required in the MPRF method. The recovery algorithm is designed based on orthogonal matching pursuit so that it can be directly applied to either Nyquist or sub-Nyquist samples. The unambiguous delay-Doppler recovery condition is derived with compressed sensing theory in noiseless settings. In particular, an upper bound to the number of targets is given, with respect to the number of samples in each pulse repetition interval and the number of transmit pulses. Simulations show that in both regimes of Nyquist and sub-Nyquist samples our method outperforms the popular MPRF approach in terms of hit rate.