The detection of the electromagnetic (EM) emission following the gravitational wave (GW) event GW170817 opened the era of multi-messenger astronomy with GWs and provided the first direct evidence that at least a fraction of binary neutron star (BNS) mergers are progenitors of short Gamma-Ray Bursts (GRBs). GRBs are also expected to emit very-high energy (VHE, > 100 GeV) photons, as proven by the recent MAGIC and H.E.S.S. observations and one of the challenges for future multi-messenger observations will be the detection of such VHE emission from GRBs in association with GWs. In this talk I will review the challenges and the status of the searches for VHE EM counterparts to GWs and discuss the prospects for future detections with next generation instruments such as the Cherenkov Telescope Array. The implications that future joint GW and VHE EM observations could have on the understanding of GRB physics will also be discussed.