You have air in your cooling system. There's a leak somewhere that has let it get low. Could be anywhere in the system; look all over for leaks, and if possible do a pressure test on it to help find it. If the heater core itself was leaking you'd probably have already noticed wet, smelly carpet.
I had to fix my ext cab for this a few months ago; the hose to the core was leaking right where it clamps onto the core, so it was leaking down the outside of the firewall in the engine compartment. But again, it doesn't have to be the core or the hoses related to it, it could be a leak anywhere in your cooling system letting the air get in.