Size-dependent magnetic single-domain versus vortex state stability of Co/Ru(0001) nanodots is explored with spin-polarized low-energy electron microscopy, analytical modeling, and micromagnetic simulations. We show that both single-domain and vortex states can be stabilized in a broad region near the phase boundary. The calculated width of the bistability region and temperature dependent heights of the energy barriers between both states agree well with our experimental findings.