Spatio-temporal forecasting plays a vital role in various domains such as transportation, meteorology, and urban management. However, existing approaches often struggle to model complex spatio-temporal dependencies effectively while maintaining computational efficiency, particularly when handling full spatio-temporal sequences. The quadratic time-space complexity of the traditional self-attention mechanism significantly limits its scalability to long-sequence tasks. To address these challenges, we propose LOSTFormer (Linear Orthogonal Spatio-Temporal Transformer) for efficient and accurate spatio-temporal forecasting. LOSTFormer constructs hierarchical embeddings across temporal, spatial, and joint spatio-temporal dimensions to enhance representation learning. Linear attention framework, a novel Learnable Orthogonal Rotation Attention (Lor-Attention) is introduced, which employs the Cayley transform to learn orthogonal rotation matrices and adaptively refine the mapping of Positive Orthogonal Random Features. Our approach can achieve linear computational complexity and effectively capture long-range and cross-dimensional dependencies in spatio-temporal data. Extensive experiments on spatio-temporal datasets demonstrate that LOSTFormer consistently outperforms state-of-the-art methods in prediction accuracy while maintaining efficiency. The code can be found on our GitHub repository( https://github.com/QAQYYC/LOSTFormer .).