Missing values in medical data present significant challenges to patient care, particularly in critical settings like the Intensive Care Unit (ICU), where accurate and timely decision-making is vital. Continuous monitoring of vital signs, such as heart rate and blood pressure, is essential for effective ICU patient management. Addressing missing values in these variables is crucial, as it provides clinicians with enhanced information for informed decisions. This paper introduces MediTHIM, a high-performance and efficient approach for medical data imputation, offering fast computation with minimal resource requirements, while relying only on past existing data. After carefully preprocessing the MIMIC-IV dataset, a recent medical dataset containing information from ICU patients including vital signs, demographic information, physical characteristics, and administered medication, we carried out a comprehensive set of experiments. Our results show that MediTHIM has the best performance while exhibiting low computation times and requiring few resources when compared against multiple competitive approaches that do not use future data. Moreover, MediTHIM also shows a stable performance with minimal fluctuations. These results were consistent across different missingness patterns analyzed and for missing percentages ranging from 1% to 50%.