As many as 600 million of the 1.9 billion adults who are overweight are obese. Obesity that is not treated immediately will be a risk factor for increasing cardiovascular, metabolic, degenerative diseases, and even death at a young age. Case Based Reasoning (CBR) can be used to estimate a person's obesity level using previous cases. The old case with the highest similarity will be the solution for the new case. Indexing methods such as the K-Means Algorithm are needed so that the search for similar cases does not involve all cases on a case base so that it can shorten the computation time at the retrieve stage and still produce optimal solutions. Cosine similarity is used to find relevant clusters of new cases and Euclidean distance similarity is used to calculate similarity between cases. Random subsampling method was used to validate the CBR system. The test results with K=2 indicate that the CBR is better than the CBR-K-Means, each of which produces an average accuracy of 88.365% and 88.270% at a threshold of 0.8. CBR-K-Means produces an average computation time at the retrieve stage of 33.55 seconds and is faster than the CBR of 35.5 seconds.