Bioremediation in hypersaline environments is particularly challenging since the microbes that tolerate such harsh environments and degrade pollutants are quite scarce. Haloarchaea, however, due to their inherent ability to grow at high salt concentrations, hold great promise for remediating the contaminated hypersaline sites. This study aimed to isolate and characterize novel haloarchaeal strains with potentials in hydrocarbon degradation. A haloarchaeal strain IM1011 was isolated from Changlu Tanggu saltern near Da Gang Oilfield in Tianjin (China) by enrichment culture in hypersaline medium containing hexadecane. It could degrade 57 ± 5.2% hexadecane (5 g/L) in the presence of 3.6 M NaCl at 37 °C within 24 days. To get further insights into the mechanisms of petroleum hydrocarbon degradation in haloarchaea, complete genome (3,778,989 bp) of IM1011 was sequenced. Phylogenetic analysis of 16S rRNA gene, RNA polymerase beta-subunit (rpoB') gene and of the complete genome suggested IM1011 to be a new species in Halorientalis genus, and the name Halorientalis hydrocarbonoclasticus sp. nov., is proposed. Notably, with insights from the IM1011 genome sequence, the involvement of diverse alkane hydroxylase enzymes and an intact ß-oxidation pathway in hexadecane biodegradation was predicted. This is the first hexadecane-degrading strain from Halorientalis genus, of which the genome sequence information would be helpful for further dissecting the hydrocarbon degradation by haloarchaea and for their application in bioremediation of oil-polluted hypersaline environments.