Real-time health monitoring of stay cables in cable-stayed bridges is necessary for timely maintenance and to avoid unforeseen fatigue damage due to vortex-induced vibration—mainly due to combination rain and wind-related dynamic loads. Conventional contact-based sensors may often malfunction in harsh weather conditions and are expensive to install and maintain. Therefore, recently, the usage of non-contact camera-based measurement is burgeoning in the domain of structural sensing. Non-contact video-based sensing provides a higher spatial resolution compared to conventional sensors along with a lower cost. Therefore, in this paper, we present a framework that uses video-based measurement as multiple sensors to reduce the estimation error in determining the real-time cable tension. First, we calculate the vibration response using the phase-based motion estimation algorithm for various locations of interest. We then intuitively fuse the data from all the locations to estimate the real-time frequency variation using a blind source separation (BSS) technique named complexity pursuit (CP). Finally, the real-time stay-cable tension is calculated from the real-time frequency history using the taut-string theory. The proposed algorithm is applied to Fred-Hartman cable-stayed bridge in Houston, Texas. The algorithm is validated using actual tension in the cable. We also show that the estimation error in the proposed sliding window-based CP framework is considerably lesser than the conventional real-time tension estimation technique using Short-time Fourier Transform (STFT). The accurate estimation of stay-cable tension from the video-based measurement shows the significant potential of the proposed framework in the domain of structural health monitoring.