Frames, shells, and hybrid structures with early damages such as early cracks often behave as extremely weak nonlinear systems, among which the nonlinearity is difficult to be detected, especially if the system response is affected by the noise. To avoid these damages becoming catastrophic failures, developing effective incipient damages detection methods is important. The nonlinear output frequency response functions (NOFRFs) and associated indexes can be considered as one kind of the prospective detection tools, which are usually determined from the established nonlinear auto-regressive with exogenous inputs (NARX) model. However, the hyperparameters in the NARX model are difficult to be determined so that the identification accuracy can’t be guaranteed. Therefore, it is important to develop more accurate methods to estimate the NOFRFs and their associated indicators for damage detection. Motivated by the powerful learning abilities of Convolutional Neural Networks (CNN) and Long Short-term Memory Networks (LSTM), a novel method based on NOFRFs and the CNN-LSTM model for detecting the early damages in structures is proposed. By applying the beat excitation, the response of the structure is divided into two components, where the approximately linear component is used to estimate the frequency characteristic of the linear component by the classical linear model, and the nonlinear component is used to establish the CNN-LSTM model. By calculating the responses of the two models, the NOFRFs and associated indexes can be accurately estimated, and then the early damage can be detected. Simulation and experimental studies verify the potential and effectiveness of the novel method proposed in this paper.