Laccases are polyphenol oxidases with widespread applications in various industries. In the present study, the laccase from Cerrena sp. HYB07 was immobilized with four methods, namely entrapment in alginate, covalently binding to chitosan as well as formation of cross-linked enzyme aggregates (CLEAs) and magnetic CLEAs (M-CLEAs). The activity recovery rates of the immobilized laccases ranged from 29% to 68%. Immobilization elevated the reaction temperature optimum and reduced substrate specificity, but not necessarily the turnover rate. pH stability of immobilized laccases was improved compared with that of the free laccase, especially at acidic pH values. Thermal inactivation of all laccases followed a simple first-order exponential decay model, and immobilized laccases displayed higher thermostability, as manifested by lower thermal inactivation rate constants and longer enzyme half-life time. Operational stability of the immobilized laccase was demonstrated by decolorization of the triphenylmethane dye malachite green (MG) at 60 °C. MG decolorization with free laccase was accompanied by a shift of the absorption peak and accumulation of a stable, colored intermediate tetradesmethyl MG, probably due to lower thermostability of the free laccase and premature termination of the degradation pathway. In contrast, complete decolorization of MG was achieved with laccase CLEAs at 60 °C.