We present a new cluster-update Monte Carlo algorithm for a fluctuating interface in the 3D Ising model. Critical slowing down is drastically reduced and the dynamical critical exponent at the roughening temperature of the 3D Ising model is found to be
zcl=0.44\ifmmode\pm\else\textpm\fi{}0.03. For the Metropolis algorithm we obtain
zMet=2.0\ifmmode\pm\else\textpm\fi{}0.1 while the Swendsen-Wang algorithm performs even worse than local updating. A new method which suppresses fluctuations in the two bulk phases is introduced to determine moments of the interfacial thickness.