We introduce variance-optimal semi-static hedging strategies for a given contingent claim. To obtain a tractable formula for the expected squared hedging error and the optimal hedging strategy we use a Fourier approach in a multidimensional factor model. We apply the theory to set up a variance-optimal semi-static hedging strategy for a variance swap in the Heston model, which is affine, in the 3/2 model, which is not. and in a market model including jumps.