This paper introduces a novel method of estimating theFourier transform of deterministic continuous-time signals from a finite number N of their nonuniformly spaced measurements. These samples, located at a mixture of deterministic and random time instants, are collected at sub-Nyquist rates since no constraints are imposed on either the bandwidth or the spectral support of the processed signal. It is shown that the proposed estimation approach converges uniformly for all frequencies at the rate N^−5 or faster. This implies that it significantly outperforms its alias-free-sampling-based predecessors, namely stratified and antithetical stratified estimates, which are shown to uniformly convergence at a rate of N^−1. Simulations are presented to demonstrate the superior performance and low complexity of the introduced technique.