Missing data is the absence of value from its place in any given dataset. It occurs for various reasons, such as equipment malfunction and erroneous entry. Handling missing data in healthcare datasets is essential for proper analysis and decision-making. Practical healthcare actions is hampered by incomplete records, undermining the validity of findings. To solve this problem, ensuring data integrity and creating thorough knowledge and robust techniques are necessary. By effectively handling it, healthcare workers will improve the quality of analysis, which will eventually result in better decision-making and increase the overall efficacy of healthcare systems and treatments by implementing efficient strategies. The paper proposes an algorithm based on Fuzzy C-Means (FCM) with a weighted membership approach that outperforms the available techniques. The contributions include a novel methodology for estimating missing values in healthcare datasets, retaining the dataset’s underlying distribution while maintaining vital information, proposed workflow, and handling numerical and categorical data types. This multistep procedure yielded more accurate results than existing methods: Mean imputation and Fuzzy C-Means with Genetic Algorithm (FCMGA). The missingness mechanism considered is missing at random (MAR) and missing not at random (MNAR). The experimentation is carried out on two benchmark datasets to assess the efficacy of the proposed approach. The proposed method improved MSE and NRMSE scores on Parkinson’s and Heart disease datasets.