This paper presents a novel approach for electrocardiogram (ECG) data compression in a healthcare monitoring system, which helps to reduce power consumption during wireless communication. The proposed ECG data compression approach consists of multilevel vector (MLV) compression, integer-linear- programming (ILP)-based compression, and Huffman coding. The MLV compression provides different compression levels for different parts of ECG signal. The ILP-based compression achieves even higher compression ratio while satisfying tolerable error rate. The Huffman coding encodes compressed ECG data without data loss. Experimental results based on the MIT-BIH arrhythmia database show that our approach result in the best quality and accuracy in terms of compression ratio and error rate compared with the previous works.