Defects on oxide surfaces play a crucial role in surface reactivity and thus it is crucial to understand their atomic and electronic structures. The defects on anatase TiO2(001)-(1 × 4) surfaces are found to be highly reactive; however, due to the surface reconstruction, the defects exhibit a complicated character in different experiments that make it very challenging to determine their atomic structures. Here we present a systematic first-principles investigation of the defects on anatase TiO2(001)-(1 × 4) surfaces based on a global-search adaptive genetic algorithm (AGA) and density functional theory (DFT). For different Ti-O ratios, we identify the low energy defect structures, investigate their electronic structure using a hybrid functional, and map their regions of stability under realistic conditions. We successfully find novel oxygen vacancy (OV) and Ti interstitial (Tiini) structures that are different from the conventional ones in terms of their charge localization, magnetic state, and their scanning-tunneling-microscopy bright-dark image signature. This provides an insight into the complex geometric and electronic structure of the surface defects, and resolves several experimental discrepancies.