We present an adaptive algorithm for the optimal phase space sampling in Monte Carlo simulations of 3D Heisenberg spin systems. Based on a golden rule of the Metropolis algorithm which states that an acceptance rate of [Formula: see text] is ideal to efficiently sample the phase space, the algorithm adaptively modifies a cone-based spin update method keeping the acceptance rate close to [Formula: see text]. We have assessed the efficiency of the adaptive algorithm through four different tests and contrasted its performance with that of other common spin update methods. In systems at low and high temperatures and anisotropies, the adaptive algorithm proved to be the most efficient for magnetization reversal and for the convergence to equilibrium of the thermal averages and the coercivity in hysteresis calculations. Thus, the adaptive algorithm can be used to significantly reduce the computational cost in Monte Carlo simulations of 3D Heisenberg spin systems.