Background: Nutritional interventions may have positive effects on sarcopenia and body composition. Objective: to evaluate the effectiveness of extra virgin olive oil (EVOO) consumption and a healthy traditional Brazilian diet (DieTBra) on improving sarcopenia indicators and reducing total body fat in severe obesity. Methods: A randomized controlled trial registered at ClinicalTrials.gov (NCT02463435) conducted with 111 severely obese participants randomized into three treatment groups—(1) EVOO (52 mL/day), (2) DieTBra, (3) DieTBra + EVOO (52 mL/day)—for 12 weeks. Body composition was assessed by dual-energy X-ray absorptiometry and sarcopenia by walking speed and handgrip strength. Results: Significant reductions in total body fat ( p = 0.041) and body weight ( p = 0.003) were observed in the DieTBra group. In the DietBra + olive oil group there was also a significant reduction in body weight (0.001) compared to the olive oil-only group. ANCOVA analyses showed reductions in total body fat in the DieTBra ( p = 0.016) and DieTBra + olive oil ( p = 0.004) groups. Individuals in the DieTBra group had significant improvements in their walking speed ( p = 0.042) and handgrip strength ( p = 0.044). Conclusions: DieTBra contributes to improvements in handgrip strength, walking speed, and total body fat in severely obese adults. The major study was registered at ClinicalTrials.gov (NCT02463435).