A compressed-sensing-technique-based Brillouin optical time-domain analysis is proposed. The Brillouin spectrum has a sparse representation in its discrete cosine transform domain, which can be successfully recovered from far fewer measurements with high probability through an orthogonal matching-pursuit algorithm. This work shows both empirically and experimentally that the amount of frequency acquisitions needed is only 30% of those required by a conventional distributed Brillouin fiber-optic sensing system with 1 MHz frequency increment in the acquisition process to obtain Brillouin spectra along an optical fiber; therefore, the number of acquisitions and the amount of data storage/transfer are greatly reduced. Moreover, the proposed method does not need any hardware modification in an existing sensing system and can also be adopted by Brillouin optical time-domain reflectometry.