Strain-based monitoring methodologies offer the crucial advantage of early-stage damage detection due to the significant effect that damage can have on the strain field in its immediate vicinity. However, to achieve this, a dense sensor grid is required to provide relevant information at critical locations of the monitored structure. In this paper, two complementary strain-based methodologies, which make use of the same monitoring hardware, are employed to monitor a historical Vierendeel truss steel railway bridge, which may be prone to brittle damage at freezing temperatures. A dense sensor grid is used to monitor strains at critical locations where high-stress concentration is expected. The strain measurements are conducted using Fiber-Bragg Gratings (FBG) and a high-accuracy, high-precision interrogator. In the first methodology, ambient dynamic strain measurements of sub-microstrain amplitude are used in Automated Operational Modal Analyses (AOMA) to determine the bridge’s modal characteristics, such as natural frequencies, damping ratios, and strain mode shapes. In the second methodology, (quasi-)static strain measurements during train passages are employed to calculate strain influence lines at the FBG locations. The sensitivity of the employed monitoring quantities to environmental and operational factors, such as temperature and changing support conditions, is investigated.