But exercise really helps. It changes what you want to eat first of all. Fat loss can be grueling or easy, depending on where your body wants to be, and exercise pushes it to the easier side.
Some of the non-calorie burning exercises have the biggest effects here. Weightlifting is almost pointless from a calorie perspective, but it really energizes weight loss. I assume that the hormonal effects are king.
Biking colossal distances is another thing that seems to lead to leaning out. In theory it should be possible just to eat through the calories burned biking, but in practice, it seems to shift the bias towards losing.
Also, the biggest problem with calories-in calories-out is that weight regain after a calorie deficit period -- even a long one -- seems to be almost a law of nature. The body seems to push extremely hard for regaining everything that has been starved off.