The wide-field camera in the advanced camera for surveys (ACS) produces very large 4096 by 4096 pixel images. We will have on-board image compression in order to reduce both the storage requirements at the telescope an the time to transmit the data to the ground. This is the first time on- board compression has been included in a Hubble Space Telescope instrument. We have developed a new lossless image compression algorithm that is designed to compress the CCD data by factors of 2 to 3.5 with the minimum possible computational load on the ACS computer. The new algorithm takes differences of adjacent pixels and then compresses the difference in pairs, producing output codes of 1, 2 or 4 bytes for each pair. The pair-coding algorithm gives slightly inferior compression to the Rice algorithm but is more than three times faster than Rice on our computer. The Rice algorithm was unfortunately too slow for us to use, but the pair-coding algorithm is fast enough to handle high data rates even on our 16-MHz 80386 computer. This paper will describe the detail of the compression algorithm and its implementation in the ACS flight software. Important implementation problems include the unpredictable data volume after compression and the need to compress four independent data streams during readout from the Wide Field Camera CCDs. We will also describe the compression performance of the new algorithm on various types of astronomical images.