The complex dielectric permittivity (CDP) of soils is used in moisture and salinity measurements. We have developed a CDP spectra determination method based on Fourier analysis of electrical signals reflected in probes of various lengths. The S11 parameters of the probes placed in samples under test were measured using a vector network analyzer, and the results were transformed into the time domain using transient-state analysis and a simulated needle pulse. The pulses reflected from the ends of the probes’ rods were extracted using a windowing function and transformed into the frequency domain. The CDP was then calculated independently at each frequency using an analytical expression. In contrast to time-domain spectroscopy techniques, knowledge of the incident signal in the soil sample is not needed. Also, no assumptions on a dielectric relaxation model of the tested materials are necessary. The method was tested on six reference materials and samples of two soils at various water contents. The accuracy of the obtained results was assessed and a rod length combination of 4 and 10 cm was selected for further use. The measurement errors for the tested reference media were determined. The method performed the best in the frequency range 0.2 to 1.0 GHz for the real part of the CDP and 0.20 to 0.85 GHz for the imaginary part. This approach may be adapted for use with a time domain reflectometry needle pulse device.