I did the same replacements (full cooling system) in the spring, and I opted to flush and clean everything before the new parts went on. Drained the system. Flushed it. Added a cleaner. Flushed it again. Took a while, but by the time I was done the water was pouring out clean enough to drink. Not that I tried.......
After that, I did the teardown, flushed the heater core seperately again, added the new parts, and filled with coolant.