Constructed wetlands (CWs) inoculated with exogenous microbes have great potential for removing pollutants in adverse environments. The rapid loss of functional bacteria and the high cost of repeated additions of inoculum, however, limit the practical application of this technology. In this study, C-F2 immobilized bacteria (i.e., immobilized salt-tolerant bacterium Alishewanella sp. F2 incorporated with a carbon source) were developed and utilized in CWs for solving the above problems. A 60-day experiment demonstrated that bioaugmented CWs (Bio-CWs) with the addition of C-F2 immobilized bacteria into the bottom gravel layer of CW microcosms (B-CF2 treatment) exhibited high nitrogen removal efficiency under a saline condition (electrical conductivity of 15 mS/ cm). We measured mean nitrate nitrogen (NO3--N) and total nitrogen (TN) removal percentages of 97.8% and 88.1%, respectively, which were significantly (p < 0.05) higher than those in Bio-CWs with microbial inoculum (MI-F2 treatment, 63.5% and 78.2%) and unbioaugmented CWs (CK, 48.7% and 67.2%). The TN content of the entire plant was significantly (p < 0.05) increased in B-CF2 (636.06 mg/microcosm) compared with CK (372.06 mg/microcosm). The relative abundances of the genera Alishewanella (i.e., the exogenous bacterium, 5.5%), Clostridium-XIVa (8.8%) and Bacteroides (21.1%) in B-CF2 were significantly (p < 0.05) higher than in MI-F2 and CK, which improved the denitrification capacity of CWs. Overall, a high denitrification efficiency and durability were achieved in the newly developed Bio-CWs (i.e., B-CF2 treatment) with immobilized bacteria under saline conditions, which provides an alternative technology for the rapid removal of nitrogen from saline wastewater.