The quality and typical characteristic of wines depends, among other factors, on the volatile organic metabolites (VOMs) that are biosynthesized by yeasts, mainly Saccharomyces cerevisiae species. The yeast strain influences the diversity and proportions of the VOMs produced during the fermentation process, as the genetic predisposition of the strains is a by-product of selective adaptation to the ecosystem. The present work reports the characterization of S. cerevisiae strains isolated from grape must, used in the Demarcated Region of Madeira (DRM) for winemaking. Yeast species were identified by amplification and by restriction fragment length polymorphism (RFLP) analysis of the region 5.8S-internal transcribed spacers (PCR-RFLP of 5.8S-ITS) of ribosomal DNA (rDNA). The strains identification was performed by analyzing the RFLP pattern of mitochondrial DNA (RFLP-mtDNA). The representative strains were selected for the characterization of the volatile profile through headspace solid-phase microextraction (HS-SPME) followed by gas chromatography-mass spectrometry (GC-MS) analysis. A total of 77 VOMs were identified. Higher alcohols, esters, and fatty acids were the major chemical families representing 63%, 16%, and 9%, respectively, in strain A and 54%, 23%, and 15% in strain B. The results indicate the influence of the strain metabolism in the production of VOMs, many of which probably participate in the aroma of the corresponding wines.