The large-amplitude rolling and capsize dynamics of vessels in random beam seas are investigated using a nonlinear single-degree-of-freedom model. Included in this model are three types of damping moments—the usual effects that are treated as linear and quadratic in the roll velocity, plus a frequency-dependent effect that captures the dissipation of energy caused by the generation of waves radiated away from the rolling vessel. The description of this type of damping requires a history-dependent term in the equations of motion. This memory effect prevents a straightforward application of the standard Melnikov method for determining capsize criteria. In this work, the Melnikov function and phase-space transport techniques are extended to derive a criterion for capsizing that can be applied to analytical models with this type of damping. Using these theoretical results, we obtain a closed-form asymptotic expression for a critical significant wave height, and this criterion is evaluated using simulation studies for a realistic set of vessel parameters.