We characterized 20 Shigella isolates with decreased susceptibility to fluoroquinolones. Most patients (80%) from whom a travel history was obtained reported travel to South or Southeast Asia. Mutations within the quinolone resistance determining regions of gyrA and parC and plasmid-mediated resistance determinants (qnrB, qnrS, and aac(6')-Ib-cr) were identified. The rise in antimicrobial resistance among Shigella isolates may necessitate the increased use of extended-spectrum cephalosporins or macrolides in some patients.