Sensing the wideband spectrum is an important process for next-generation wireless communication systems. Spectrum sensing primarily aims at detecting unused spectrum holes over wide frequency bands so that secondary users can use them to meet their requirements in terms of quality-of-service. However, this sensing process requires a great deal of time, which is not acceptable for timely communications. In addition, the sensing measurements are often affected by uncertainty. In this paper, we propose an approach based on Bayesian compressive sensing to speed up the process of sensing and to handle uncertainty. This approach takes only a few measurements using a Toeplitz matrix, recovers the wideband signal from a few measurements using Bayesian compressive sensing via fast Laplace prior, and detects either the presence or absence of the primary user using an autocorrelation-based detection method. The proposed approach was implemented using GNU Radio software and Universal Software Radio Peripheral units and was tested on real-world signals. The results show that the proposed approach speeds up the sensing process by minimizing the number of samples while achieving the same performance as Nyquist-based sensing techniques regarding both the probabilities of detection and false alarm.