St. Augustinegrass [Stenotaphrum secundatum (Walt.) Kuntze] is a warm-season turfgrass commonly grown in the southern USA. In this study, the first linkage map for all nine haploid chromosomes of the species was constructed for cultivar ‘Raleigh’ and cultivar ‘Seville’ using a pseudo-F2 mapping strategy. A total of 160 simple sequence repeat markers were mapped to nine linkage groups (LGs) covering a total distance of 1176.24 cM. To demonstrate the usefulness of the map, quantitative trait loci (QTL) were mapped controlling field winter survival, laboratory-based freeze tolerance, and turf quality traits. Multiple genomic regions associated with these traits were identified. Moreover, overlapping QTL were found for winterkill and spring green up on LG 3 (99.21 cM); turf quality, turf density, and leaf texture on LG 3 (68.57–69.50 cM); and surviving green tissue and regrowth on LGs 1 (38.31 cM), 3 (77.70 cM), 6 (49.51 cM), and 9 (34.20 cM). Additional regions, where QTL identified in both field and laboratory-based/controlled environment freeze testing co-located, provided strong support that these regions are good candidates for true gene locations. These results present the first complete linkage map produced for St. Augustinegrass, providing a template for further genetic mapping. Additionally, markers linked to the QTL identified may be useful to breeders for transferring these traits into new breeding lines and cultivars.