A numerical scheme that uses multi-frequency Newton iterations to reconstruct a rough surface profile between two dielectric media is proposed. At each frequency sample, the scheme employs Newton iterations to solve the nonlinear inverse scattering problem. At every iteration, the Newton step is computed by solving a linear system that involves the Frechet derivative of the integral operator, which represents the scattered fields, and the difference between these fields and the measurements. This linear system is regularized using the Tikhonov method. The multi-frequency data is accounted for in a recursive manner. More specifically, the profile reconstructed at a given frequency is used as an initial guess for the iterations at the next frequency. The effectiveness of the proposed method is validated through numerical examples, which demonstrate its ability to accurately reconstruct surface profiles even in the presence of measurement noise. The results also show the superiority of the multi-frequency approach over single-frequency reconstructions, particularly in terms of handling surfaces with sharp variations.