The goal of this study was to develop a startup strategy for a high-rate anaerobic ammonium oxidation (anammox) reactor to treat waste brine with high concentrations of ammonium from a natural gas plant. An upflow anaerobic sludge blanket (UASB) anammox reactor with an effective volume of 294 L was fed continuously with waste brine with a salinity of 3% and a NH4+ concentration of 180 mg-N/L, as well as a NaNO2 solution. By inoculating a methanogenic granular biomass as a biomass carrier, the reactor attained the maximum volumetric nitrogen removal rate (NRR) of 10.7 kg-N/m3/day on day 209, which was 1.7 times higher than the highest reported NRR for wastewater of comparable salinity. High-throughput sequencing of 16S rRNA gene amplicons revealed that Candidatus Scalindua wagneri was enriched successfully in granules in the UASB, and it replaced Methanosaeta and became dominant in the granule. The inhibitory effect of NO2- on the anammox reaction in the granules was assessed by a 15N tracer method, and the results showed that anammox activity was maintained at 60% after exposure to 300 mg-N/L of NO2- for 24 h. Compared with previous studies of the susceptibilities of Candidatus Brocadia and Candidatus Kuenenia to NO2-, the enriched marine anammox bacteria were proven to have comparable or even higher tolerances for high NO2- concentrations after a long exposure.