Prestressed concrete bridges experience complex loading conditions throughout their lifespan, which affects their capacity and overall performance. Understanding bridge responses under varying loads is crucial for ensuring safety and optimal performance. To achieve this, numerous sensors are deployed to monitor the bridge’s structural behavior during its operation. Environmental factors, such as temperature changes, can have a significant impact on the structural responses of these bridges, often comparable to or exceeding the effects caused by actual damage. Therefore, it is crucial to differentiate between structural changes due to environmental conditions and those due to structural damage. Traditional filtering methods like Principal Component Analysis (PCA) and Fast Fourier Transform (FFT) struggle to adapt to multi-scale variations in bridge responses, requiring manual tuning. This paper introduces a multi-scale Matrix Profiling (MP) as a novel, scalable approach for anomaly detection in Structural Health Monitoring (SHM). Despite its success in other applications, MP has not been applied in structural engineering. By leveraging multi-scale MP, we efficiently differentiate between environmental effects and structural anomalies. By integrating MP with Artificial Neural Networks (ANNs), we develop a data-driven framework for anomaly detection, enhancing long-term monitoring and decision-making for bridge maintenance and safety. Our approach, tested on four years of sensor data from a prestressed concrete bridge in Northern Sweden, identifies common patterns and anomalies, effectively distinguishing environmental variations from potential structural damage.