The aim of this study was isolation and characterization of heterotrophic bacteria capable of ammonium and nitrite removal at 15 °C (optimal temperature for growing rainbow trout Oncorhynchus mykiss). Environmental isolates were grown in liquid media containing ammonium or nitrite, and best strains in terms of growth and ammonium or nitrite removal were identified via 16S rRNA sequencing. Dyadobacter sp. (no. 68) and Janthinobacterium sp. (no. 100) were selected for optimal adaptation to growth at 15 °C and best ammonium and nitrite removal (P <0.05), respectively. A heterotrophic ammonium and nitrite removal (HAN) microbial complex, containing selected strains, was prepared and applied in a trout culture system. After 10 days, the effect of microbial HAN complex was investigated in terms of ammonium and nitrite removal, as well as stress and immune indices present in the plasma of cultivated trout. Compared to a standard cultivation setup, addition of the HAN complex had a clear beneficial effect on keeping the un-ionized ammonia and nitrite level below prescribed standards (P <0.05). This resulted in reduction of stress and immune reactions of cultivated fish (P <0.05), leading to an augmentation of final weight and survival. Application of the selected microbial complex resulted in a significant improvement of the aquaculture ecosystem.