Recently, hyperspectral image (HSI) classification methods based on deep learning (DL) have demonstrated excellent performance. However, these DL methods still face two major challenges. One is that they require a large number of labeled samples, and the other is that training parameters take a lot of time. In this article, we propose a dual-branch deep stochastic adaptive Fourier decomposition (SAFD) network (DSAFDNet) to alleviate the aforementioned two issues in HSI classification applications. SAFD is a newly developed signal processing tool with a solid mathematical foundation. It can be used to find common filters (i.e., convolution kernels) of a set of random signals (RSs) or multisignals. Since the convolution kernels obtained by SAFD decomposition are complex numbers, few DL methods directly deal with such complex convolution kernels. To this end, we propose a dual-branch network to extract deep features from HSIs using both real and imaginary parts of convolutional kernels. After deep feature extraction using DSAFDNet, we further investigate the classification performance of different classifiers on the extracted features. Experimental results show that the proposed method outperforms some HSI classification methods with similar principles. Moreover, compared with other state-of-the-art DL methods, the proposed method can achieve better classification performance.