Background: MR guided High Intensity Focused Ultrasound (MRgHIFU) has emerged as a leading noninvasive modality for prostate cancer treatments. However, due to the long acquisition time, the MR guidance is limited to very few 2D slices. This coverage is not sufficient for monitoring the entire prostate gland, and dangerous temperature rise might occur in unmonitored slices. Methods: A method for accelerating prostate MRgHIFU is proposed. The acquisition time is reduced by significant subsampling of k-space, while using parallel multi-coil imaging, and implementing a novel Compressed Sensing (CS) reconstruction scheme. The CS reconstruction uniquely utilizes a-priori knowledge about the spatio-temporal data sparsity and reconstructs the complex differences between pre-heating and post-heating datasets. The method was validated through retrospective experiments with in-vivo data obtained in clinical procedures. Results: The experiments with in-vivo acquired data demonstrated that the proposed method produces very accurate temperature maps from highly subsampled data, with reduction factors ranging from R=2 to R=10. Furthermore, the proposed method outperforms current state-of-the-art methods. The proposed method runs faster and obtains significantly smaller errors. Conclusion: The proposed method is suitable for accelerating prostate MRgHIFU monitoring via significant k-space undersampling and Compressed Sensing reconstruction. Implementation of this method in clinical procedures may enable temperature monitoring in larger tissue volumes and may hence improve treatment safety and efficacy significantly.