In this paper, the structural stability of a fast-spinning small body is investigated. In particular, a nonlinear yield condition in tensile stress is applied to estimate the required cohesion in a fast-spinning small body. The least upper bound of required cohesion is investigated for both ellipsoid and irregular shape models. The stress state of a fast-spinning ellipsoid is discussed analytically, and the effects of spin rates and size ratios are analyzed. For an irregularly shaped body, an element average stress method is developed to estimate the range of stress of any element in the body, where only self-gravity and centrifugal force are considered. The maximum tensile stress in the whole body is used to solve the required cohesion. Finally, the proposed methods are applied to different asteroid shape models. The result shows that the least upper bound of cohesion is mainly determined by the spin rate and length of the major axis, but an irregular shape will change the stress distribution and cause a stressed surface. The required cohesion of a fast-spinning small body varies between tens to 1000 Pa. The methods developed in this paper can rapidly provide a conservative lower bound on the cohesion in a fast-spinning body and qualitatively show the distribution of stress, which provides an effective way to study the structural stability of fast-spinning bodies of those bodies.