Mechanically interlocked molecules represent chemical architectures whose composing elements are linked because of their topology instead of covalent bonds [1]. Among them, the catenanes are analogous to an ensemble of interlaced rings, globally locked yet locally independent. We disclose in this work the equivalent of such exotic molecules in the realm of nonlinear Photonics. They appear as interlocked bound states of localized structures (LSs) found in the temporal output of a Vertical-Cavity Surface-Emitting Laser (VCSEL) in presence of a point-wise nonlocality.