Successful elimination of high concentrations of N–NOx− (up to 250 mg/L) from high salinity wastewaters (up to 35 g/L Cl− + 17 g/L SO4 2−) originating from desulphurization process within coal power stations was achieved using pure cultures of denitrifying bacteria encapsulated in porous polyvinyl alcohol lenses (so called Lentikats Biocatalyst, LB). Laboratory batch tests revealed inhibitory influence of the raw wastewater on the denitrification activity, which was partially mitigated by the addition of P–PO4 3−. In following continuous tests, the denitrification activities reached the range 150–450 mg N/h/kg LB, i.e., values suitable for industrial scale applications. The higher activities were achieved under a lower salinity, higher N–NOx− influent concentrations and a prolonged retention time. The effluent N–NOx− concentrations were below the determination limit of 5 mg/L. After a period of 3 months, a significant decrease of denitrification activity of Lentikats Biocatalyst was observed. Addition of nutrients into the wastewater enabled fast regeneration of the initial activity. The overall results proved the applicability of Lentikats Biocatalysts for the removal of nitrates from high-salinity desulphurization water and other industrial wastewaters of similar character.