Immobilization of biocatalysts is a current topic in research enabling the easy recovery of catalysts from the reaction medium after the reaction, and it is often accompanied by a stabilization of the catalysts, which enables recycling. Within our ongoing research on the utilization of aldoxime dehydratases in the cyanide-free synthesis of nitriles through dehydration of readily available aldoximes, a screening of different immobilization methods for free enzymes was performed. The applied immobilization methods are based on covalent binding and hydrophobic interactions of the enzyme with the carrier material and whole-cell immobilization in calcium alginate beads with and without subsequent coating. In our study, we found that the immobilization with purified free aldoxime dehydratases from OxdRE (Rhodococcus erythropolis) and OxdB (Bacillus sp. strain OxB-1) leads to high immobilization efficiencies, but also to a strong loss of activity with a residual activity of <20%, regardless of the carrier material used. However, when using whole cells for immobilization instead of purified enzymes, we could increase the residual activity significantly. Escherichia coli BL21(DE3)-CodonPlus-RIL OxdRE and OxdB whole cells were entrapped in calcium alginate beads and coated with silica using tetraethylorthosilicate (TEOS), leading to immobilized catalysts with up to 75% residual activity and a higher stability compared to the free whole cells. Even after three rounds of recycling, which corresponds to a 3 d reaction time, the immobilized OxdB whole cells showed a residual activity of 85%.