In this paper, we present a new method to measure the complex dielectric permittivity of materials-under-test with an open-ended coaxial probe. The method, which explicitly takes measurement noise into account to enhance the stability of the measurements, is formulated based on the maximum likelihood estimation of the Debye parameters from calibrated reflection measurements performed at the aperture of the probe. In particular, the measurement noises at different frequencies are approximated with independent Gaussian distributions. To estimate the mean and the standard deviation of the mentioned probability distributions at each frequency, the differences among repetitive measurements of a reference sample are analyzed. Later, these statistical distributions are enforced into a cost functional to derive an optimization scheme based on the maximum likelihood estimation. Finally, the cost functional is iteratively minimized with a second-order Newton-based technique to retrieve the Debye relaxation parameters of a material. We further experimentally verified the method with various liquid samples and the accuracy of the obtained results is compared with the previous works.