The recent detection of gravitational waves (GWs) and electromagnetic (EM) waves originating from the same source marks the start of a new multi-messenger era in astronomy. The arrival time difference between the GW and EM signal can be used to constrain differences in their propagation speed, and thus gravitational theories. We study to what extent a non-zero time delay can be explained by gravitational lensing when the line of sight to the source passes near a massive object. For galaxy scale lenses, this delay becomes relevant for GWs with frequencies between $10^{-6}$ and $10^{-9}$ Hz, sourced by super massive binary black-holes. In addition to GWs detectable by Pulsar Timing Arrays (PTAs), we expect to find also a unique and recognizable EM signal. We show that the delay between the GW and EM signal can be of the order of days to months; within reach of future observations. The effect may become important in future multi-messenger astronomy probing of gravitational propagation and interactions.