Hyperspectral remote sensing has been widely utilized in high-resolution climate observation, environment monitoring, resource mapping, etc. However, it brings undesirable difficulties for transmission and storage due to the huge amount of the data. Lossless compression has been demonstrated to be an efficient strategy to solve these problems. In this paper, a novel Band Regrouping based Lossless Compression (BRLlC) algorithm is proposed for lossless compression of hyperspectral images. The affinity propagation clustering algorithm, which can achieve adaptive clustering with high efficiency, is firstly applied to classify all of the hyperspectral bands into several groups based on the inter-band correlation matrix of hyperspectral images. Consequently, hyperspectral bands with high correlation are clustered into one group so that the prediction efficiency in each group can be greatly enhanced. In addition, a linear prediction algorithm based on context prediction is applied to the hyperspectral images in each group followed by arithmetic coding. Experimental results demonstrate that the proposed algorithm outperforms some classic lossless compression algorithms in terms of bit per pixel per band and in terms of processing performance.