This paper derives a formula to determine the minimum detectable damage based on ambient vibration data. It is a key element to analyze which damage scenarios can be detected before a monitoring system is installed. For the analysis, vibration data from the reference structure as well as a finite element model are required. Minimum detectability is defined by adopting a code-based reliability concept that considers the probability of detection and the probability of false alarms. The results demonstrate that the minimum detectable damage depends on three elements: the uncertainty of the damage-sensitive feature (which decreases with increasing measurement duration), its sensitivity towards model-based design parameters, and the reliability requirements regarding the damage diagnosis results. The theory is developed for the stochastic subspace-based damage detection method but can be applied to any damage-sensitive feature provided its sensitivities and statistical properties can be characterized. For proof of concept, the minimum detectable change in stiffness and mass of a pin-supported beam are analyzed in a numerical and experimental study, respectively. The predictions with the developed approach appear to be accurate and robust to noise effects for both simulated and real data.