Correlated red noise recently reported from pulsar timing observations may be an indication of stochastic gravitational waves emitted by cosmic strings that formed during a phase transition near the Grand Unification energy scale. Unfortunately, known probes of cosmic strings, namely the Cosmic Microwave Background anisotropies and string lensing of extragalactic galaxies, are not sensitive enough for such low string tensions. We show that strong gravitational lensing of Fast Radio Bursts (FRBs) by cosmic strings is a potentially unambiguous avenue to probe that range of string tension values. Other new physics that can be probed by FRBs will also be briefly discussed.