This study presents a novel methodology for structural health monitoring (SHM), using a self-powered sensing concept, within the context of machine learning (ML) and pattern recognition (PR). The proposed method is based on the interpretation of data provided by a self-powered discrete analog wireless sensor used to measure the structural response along with an energy-efficient pulse switching technology employed for data communication. A system using such an energy-aware sensing technology demands dealing with power budgets for sensing and communication of binary data, resulting in missing and incomplete data received at the SHM processor. Numerical studies were conducted on an aircraft wing stabilizer subjected to dynamic loading to evaluate and verify the performance of the proposed methodology. Damage was simulated on a finite element model by decreasing stiffness in a region of the stabilizer’s skin. Several features, i.e., patterns or images, were extracted from the strain response of the stabilizer. The obtained features were fed into a ML methodology incorporating low-rank matrix decomposition and PR for damage diagnosis of the wing. Different ML algorithms, including support vector machine, k-nearest neighbor, and artificial neural networks, were integrated within the learning methodology to assess the performance of the damage detection approach. Different levels of harvested energy were also considered to evaluate the robustness of the damage detection method with respect to such variations. Further, reliability of the proposed methodology was evaluated through an uncertainty analysis. Results demonstrate that the developed SHM methodology employing ML is efficient in detecting damage from a novel self-powered sensor network, even with noisy and incomplete binary data.