To cope with bacterial infections, broad-spectrum antibiotics such as sulfonamides have been largely used for intensive coastal aquaculture. Sulfonamides are stable and difficult to remove by conventional wastewater treatment. Environmental pollution will occur if sulfonamide-containing aquaculture wastewater is discharged into rivers and oceans. In this study, high salinity-tolerant bacterial strains A12 and L with sulfamethoxazole (SMX)-degrading ability from milkfish (Chanos chanos) culture pond sediments with SMX were isolated, identified, and characterized. The degradation of SMX and the changes in the bacterial community in milkfish culture pond sediments were assessed. Phylogenetic analysis using 16S rRNA gene sequences suggested that bacterial strain A12 was very close (99% sequence identity) to Vibrio sp., and bacterial strain L was very close (99% sequence identity) to Pseudomonas sp. Aerobic and anaerobic batch and continuous SMX addition experiments indicated that bacterial strains A12 and L could enhance SMX degradation in milkfish culture pond sediments. Different microbial community compositions under aerobic and anaerobic conditions exhibited different SMX-degrading abilities. The results of this study suggest that bacterial strains A12 and L provide a solution for treatment of wastewater and sediment from SMX-contaminated high salinity milkfish culture ponds.