No offense, and knowing nothing about your situation, the experience you describe suggests to me that you are so out of shape, you haven't experienced the point where the sense of well-being starts to move the other way.
I've been there, and I've gotten over that hump (and fallen back into it, several times), but it took a lot more work than most people seem to assume it will. Not in terms of effort - if anything, overdoing intensity early on can be sabotaging, since it >will< make you feel like shit, but in terms of consistency. People often throw themselves headlong into an exercise program, overdo it, and make themselves feel like crap, fall off the wagon, and never really experience the benefits, where what really works is consistent, constant improvement.
High intensity intervale training, for example, really isn't all that 'High Intensity' if done correctly. The goal is to keep your heart rate at about ~80% (I forget the number) of maximum. This is actually quite a achievable with only slightly more effort than feels 'easy', but because of the words 'High Intensity' (and a lot of shitty journalism around the concept) people who aren't actively monitoring their heart rate throw themselves at it so hard that can't sustain the effort for more than a dozen paces.
The key thing is to be putting yourself just at the edge of discomfort, consistently, for months. Just a few more pounts in your 5x5 weightlifting routine, or simply keeping your HR monitor at 150 bpm or so for a minute at a time.