Due to the difficulties caused by large satellite cloud image data with limited transmission channel and storage space, an approach of block compressed sensing of satellite cloud images is proposed based on Tetrolet transform. This approach introduces Tetrolet transform into the sparse representation step of compressed sensing which can depict the detail and texture structure of satellite cloud image well, and combines block compressed sensing with smooth projection Landweber iteration method to accomplish image reconstruction which can improve the computational efficiency. Meanwhile, in order to further improve the quality of reconstructed cloud images, another improvement scheme for the sparse representation of cloud images is proposed. Firstly, a layer of Laplacian pyramid decomposition of the original image is taken, and the low frequency component and high frequency component obtained are divided into blocks and sampled respectively. Then, the low frequency component is represented by Wavelet transform, while the high frequency component is represented by Tetrolet transform, which can not only play the advantage of different sparse representation, but also make full use of the advantages of Tetrolet transform in expressing the important information of cloud images, such as directional texture and edge information. The experimental results show that the reconstruction quality of the proposed method is obviously superior to Tetrolet, DWT, Contourlet and DCT sparse representation methods under the same sampling rate.