Host-guest complex formation on electrode surfaces can be used to immobilize molecular electrocatalysts. A detailed study on the formation of such HGCs on gold, along with DFT calculations, shows a strong binding of the guests to the surface-bound cyclodextrin hosts. By demonstrating the catalytic activity of HGC-bound guests in both organic and aqueous electrolyte, our experiments show the versatility of using this approach to immobilize different electrocatalytic guests for operation in different chemical environments. The high stability of the host structures on the electrode surface allows for regeneration of the electrodes by re-adsorption of fresh catalyst guests, which overcomes one of the largest challenges in immobilized molecular electrocatalysis: the electrodes can be reused even when the catalyst molecules have degraded.