Fast discrete orthonormal Stockwell transform. We present an efficient method for computing the discrete orthonormal Stockwell transform (DOST). The Stockwell transform (ST) is a time-frequency decomposition transform that is showing great promise in various applications, but is limited because its computation is infeasible for most applications. The DOST is a nonredundant version of the ST, solving many of the memory and computational issues. However, computing the DOST of a signal of length N using basis vectors is still 𝒪(N 2 ). The computational complexity of our method is 𝒪(NlogN), putting it in the same category as the FFT. The algorithm is based on a simple decomposition of the DOST matrix. We also explore the way to gain conjugate symmetry for the DOST and propose a variation of the parameters that exhibits symmetry, akin to the conjugate symmetry of the FFT of a real-valued signal. Our fast method works equally well on this symmetric DOST. In this paper, we provide a mathematical proof of our results and derive that the computational complexity of our algorithm is 𝒪(NlogN). Timing tests also confirm that the new method is orders-of-magnitude faster than the brute-force DOST, and they demonstrate that our fast DOST is indeed 𝒪(NlogN) in complexity.