Aims: To investigate the effects of a 6-month supplementation with calcium and cholecalciferol on biochemical parameters and muscle strength of institutionalized elderly. Methods: This prospective, double-blind, placebo-controlled, randomized trial included Brazilian institutionalized people ≥60 years of age receiving a 6-month supplementation (December to May) of daily calcium plus monthly placebo (calcium/placebo group) or daily calcium plus oral cholecalciferol (150,000 IU once a month during the first 2 months, followed by 90,000 IU once a month for the last 4 months; calcium/vitamin D group). Fasting blood samples for 25(OH)D, PTH and calcium determination were collected (n = 56) and muscle tests were performed (n = 46) to measure the strength of hip flexors (SHF) and knee extensors (SKE) before (baseline) and after the 6-month intervention (6 months). Results: Due to seasonal variations, serum 25(OH)D significantly enhanced in both groups after treatment, but the calcium/vitamin D group had significantly higher 25 (OH)D levels than the calcium/placebo group (84 vs. 33%, respectively; p < 0.0001). No cases of hypercalcemia were observed. While the calcium/placebo group showed no improvement in SHF and SKE at 6 months (p = 0.93 and p = 0.61, respectively), SHF was increased in the calcium/vitamin D group by 16.4% (p = 0.0001) and SKE by 24.6% (p = 0.0007). Conclusions: The suggested cholecalciferol supplementation was safe and efficient in enhancing 25(OH)D levels and lower limb muscle strength in the elderly, in the absence of any regular physical exercise practice.