Background: Tostado is a traditional sweet wine from the Designations of Origins (DOs) of Ribeiro and Valdeorras in Galicia (NW Spain). The harvested grapes are air-dried and pressed to increase the concentrations of sugars, acids, and flavour compounds. Therefore, knowledge of the yeasts involved in fermentation under these conditions is essential to guarantee the quality and uniqueness of the valuable, distinctive, and expensive Tostado wines. Methods: Saccharomyces and non-Saccharomyces yeasts were identified using Wallerstein Laboratory (WL) Nutrient Agar and lysine plating, followed by polymerase chain reaction (PCR) amplification, enzymatic digestion, and sequencing. Saccharomyces cerevisiae isolates were further characterised at the strain level using mitochondrial DNA (mtDNA) restriction fragment length polymorphism (RFLP). Statistical analyses were also performed, including different diversity indices, Similarity Percentage (SIMPER) analysis, principal component analysis (PCA), neighbor-joining clustering, parsimony–phylogram, and network plot. In addition, the total acidity, volatile acidity, reducing sugars, and alcoholic strength by volume of the Tostado wines were analysed. Results: A wide diversity of autochthonous yeasts was found, which were predominantly species of oenological relevance, such as Lachancea thermotolerans, Starmerella bacillaris, Hanseniaspora uvarum, Debaryomyces hansenii, Torulaspora delbrueckii, Pichia spp., and Saccharomyces cerevisiae from the must and paste stages of Tostado wine. In addition, 19 different S. cerevisiae strains were identified. This high yeast diversity, which changed from the early stages of fermentation, could contribute to the distinctive characteristics observed in Tostado wine. Conclusions: Characteristic and differentiating chemical and microbiological profiles were found as early as the pre-fermentation stages, which adds value to these special wines that have rarely been studied.