Palmprint recognition has shown great value for biometric recognition due to its advantages of good hygiene, semi-privacy and low invasiveness. However, most existing palmprint recognition studies focus only on homogeneous palmprint recognition, where comparing palmprint images are collected under similar conditions with small domain gaps. To address the problem of matching heterogeneous palmprint images captured under the visible light (VIS) and the near-infrared (NIR) spectrum with large domain gaps, in this paper, we propose a Fourier-based feature learning network (FFLNet) for VIS-NIR heterogeneous palmprint recognition. First, we extract the multi-scale shallow representations of heterogeneous palmprint images via three vanilla convolution layers. Then, we convert the shallow palmprint feature maps into frequency-specific representations via Fourier transform to separate different layers of palmprint features, and exploit the underlying common and palmprint-specific frequency information of heterogeneous palmprint images. This effectively reduces the modality gap of heterogeneous palmprint images at the feature level. After that, we convert the common frequency-specific feature maps back to the spatial domain to learn the identity-invariant discriminative features via residual convolution for heterogeneous palmprint recognition. Extensive experimental results on three challenging heterogeneous palmprint databases clearly demonstrate the effectiveness of the proposed FFLNet for VIS-NIR heterogeneous palmprint recognition.