Background Halorubrum lacusprofundi is a cold-adapted halophilic archaeon isolated from Deep Lake, a perennially cold and hypersaline lake in Antarctica. Its genome sequencing project was recently completed, providing access to many genes predicted to encode polyextremophilic enzymes active in both extremely high salinity and cold temperatures. Results Analysis of the genome sequence of H. lacusprofundi showed a gene cluster for carbohydrate utilization containing a glycoside hydrolase family 42 β-galactosidase gene, named bga. In order to study the biochemical properties of the β-galactosidase enzyme, the bga gene was PCR amplified, cloned, and expressed in the genetically tractable haloarchaeon Halobacterium sp. NRC-1 under the control of a cold shock protein (cspD2) gene promoter. The recombinant β-galactosidase protein was produced at 20-fold higher levels compared to H. lacusprofundi, purified using gel filtration and hydrophobic interaction chromatography, and identified by SDS-PAGE, LC-MS/MS, and ONPG hydrolysis activity. The purified enzyme was found to be active over a wide temperature range (−5 to 60°C) with an optimum of 50°C, and 10% of its maximum activity at 4°C. The enzyme also exhibited extremely halophilic character, with maximal activity in either 4 M NaCl or KCl. The polyextremophilic β-galactosidase was also stable and active in 10–20% alcohol-aqueous solutions, containing methanol, ethanol, n-butanol, or isoamyl alcohol. Conclusion The H. lacusprofundi β-galactosidase is a polyextremophilic enzyme active in high salt concentrations and low and high temperature. The enzyme is also active in aqueous-organic mixed solvents, with potential applications in synthetic chemistry. H. lacuprofundi proteins represent a significant biotechnology resource and for developing insights into enzyme catalysis under water limiting conditions. This study provides a system for better understanding how H. lacusprofundi is successful in a perennially cold, hypersaline environment, with relevance to astrobiology.