We present a stochastic cluster algorithm that drastically reduces critical slowing down for Z 2 lattice gauge theory in three dimensions. The dynamical exponent z is reduced from z > 2 (standard Metropolis algorithm) to z~0.73. The Monte Carlo pseudodynamics acts on the gauge-invariant flux tubes that are known to be the relevant large-scale low-energy excitations. A comparison of our results with known results for the 3D Ising model and ~b 4 model supports the conjecture of universality classes for stochastic cluster algorithms.