Major issues in video data transfer over the internet are security and speed. For fast transmission over the network, the video data should be compressed before transmission. Joint compression and encryption algorithms employ compression before encryption for secured and fast data transfer over the internet. In this paper, a joint compression and encryption algorithm, Puzzle Fast Random Bit Encryption (PFRBE) algorithm, is proposed. As the proposed solution employs multi-level encryption along with key encryption, it is more secured than existing algorithms. Results obtained are compared with some popular joint compression and encryption algorithms such as Video Encryption Algorithm (VEA) and Real-time Video Encryption Algorithm (RVEA). Our analysis shows that the proposed solution, PFRBE, takes less CPU time and consumes less memory when compared to existing joint compression and encryption algorithms. © 2005 - 2012 JATIT & LLS.