Prestressed stayed columns (PSCs) are structural systems whose compressive load-carrying capacity is enhanced through pre-tensioned cable stays. Much research has demonstrated that PSCs buckle subcritically when their prestressing levels maximise the critical buckling load of the theoretically perfect arrangement. Erosion of the pre-tensioned cables’ effectiveness (e.g. through creep or corrosion) can thus lead to sudden collapse. The present goal is to develop a structural health monitoring (SHM) technique for in-service PSCs that returns the current structural utilisation factor based on selected probing measurements. Hence, PSCs with different cable erosion and varying compression levels are probed in the pre-buckling range within the numerical setting through a nonlinear finite element model. In contrast with previous work, it is found presently that the initial lateral stiffness from probing a PSC provides a suitable health index for in-service structures. A machine learning based surrogate is trained on simulated data of the loading factor, cable erosion, and probing indices; it is then used as a predictive tool to return the current utilisation factor for PSCs alongside the level of cable erosion given probing measurements, showing excellent accuracy and thus provides confidence that an SHM technique based on probing is indeed feasible.