The interplay between bacterial antimicrobial susceptibility, phylogenetics and patient outcome is poorly understood. During a typhoid clinical treatment trial in Nepal, we observed several treatment failures and isolated highly fluoroquinolone-resistant Salmonella Typhi (S. Typhi). Seventy-eight S. Typhi isolates were genome sequenced and clinical observations, treatment failures and fever clearance times (FCTs) were stratified by lineage. Most fluoroquinolone-resistant S. Typhi belonged to a specific H58 subclade. Treatment failure with S. Typhi-H58 was significantly less frequent with ceftriaxone (3/31; 9.7%) than gatifloxacin (15/34; 44.1%)(Hazard Ratio 0.19, p=0.002). Further, for gatifloxacin-treated patients, those infected with fluoroquinolone-resistant organisms had significantly higher median FCTs (8.2 days) than those infected with susceptible (2.96) or intermediately resistant organisms (4.01)(p<0.001). H58 is the dominant S. Typhi clade internationally, but there are no data regarding disease outcome with this organism. We report an emergent new subclade of S. Typhi-H58 that is associated with fluoroquinolone treatment failure.