Background: Bio-signals are the essential data that smart healthcare systems require for diagnosing and treating common diseases. However, the amount of these signals that need to be processed and analyzed by healthcare systems is huge. Dealing with such a vast amount of data presents difficulties, such as the need for high storage and transmission capabilities. In addition, retaining the most useful clinical information in the input signal is essential while applying compression. Methods: This paper proposes an algorithm for the efficient compression of bio-signals for IoMT applications. This algorithm extracts the features of the input signal using block-based HWT and then selects the most important features for reconstruction using the novel COVIDOA. Results: We utilized two different public datasets for evaluation: MIT-BIH arrhythmia and EEG Motor Movement/Imagery, for ECG and EEG signals, respectively. The proposed algorithm’s average values for CR, PRD, NCC, and QS are 18.06, 0.2470, 0.9467, and 85.366 for ECG signals and 12.6668, 0.4014, 0.9187, and 32.4809 for EEG signals. Further, the proposed algorithm shows its efficiency over other existing techniques regarding processing time. Conclusions: Experiments show that the proposed method successfully achieved a high CR while maintaining an excellent level of signal reconstruction in addition to its reduced processing time compared with the existing techniques.