Using surface x-ray diffraction (SXRD), quantitative low-energy electron diffraction (LEED), and density-functional theory (DFT) calculations, we have determined the structure of the (4×1) reconstruction formed by sputtering and annealing of the SnO_{2}(110) surface. We find that the reconstruction consists of an ordered arrangement of Sn_{3}O_{3} clusters bound atop the bulk-terminated SnO_{2}(110) surface. The model was found by application of a DFT-based evolutionary algorithm with surface compositions based on SXRD, and shows excellent agreement with LEED and with previously published scanning tunneling microscopy measurements. The model proposed previously consisting of in-plane oxygen vacancies is thus shown to be incorrect, and our result suggests instead that Sn(II) species in interstitial positions are the more relevant features of reduced SnO_{2}(110) surfaces.