Side-channel attacks pose a significant threat to cryptographic implementations by exploiting physical information to infer secret keys. Trace segmentation, which involves identifying key-related operations within complete side-channel traces, is a necessary prerequisite for side-channel attacks. Existing trace segmentation methods exhibit several limitations, including reliance on human expertise, inability to address random delay countermeasures, and excessive overhead. In this paper, we propose TS-Seg, a side-channel trace segmentation method based on temporal-spatial feature fusion. TS-Seg extracts temporal and spatial features from side-channel traces by employing a novel model architecture and loss function, thereby enabling automated and accurate trace segmentation. We evaluate TS-Seg on three post-quantum cryptographic algorithms (NTRU, Saber, and Kyber) implemented on an ARM Cortex-M4 embedded processor, achieving a segmentation accuracy of 100%, both with and without random delay countermeasures. We integrate TS-Seg into profiling attacks to assess its practical effectiveness. Compared to commonly used correlation coefficient-based segmentation methods, TS-Seg improves the accuracy of recovering individual key coefficients by 0.35% to 13.95%. Finally, we compare the functionality of TS-Seg with four state-of-the-art trace segmentation schemes, demonstrating its superiority in terms of automation, capability to handle random delay countermeasures, and acceptable overhead.