Por aquí realicé una breve explicación del tema "cabeceras HTTP" (que es lo que envias con la función header()".
http://www.forosdelweb.com/1375512-post.html
Como ahí comento .. una función header() tan sólo envia "cabeceras HTTP" al cliente (navegador en tu caso), .. estas cabeceras son de cualquier tipo .. no sólo para "redireccionar" como es el caso típico de "Location" .. hasta una "cookie" es una cabecera HTTP sólo que se "envia" con otra función (setcookie() ...)
El hecho de que se diga mucho "la función header() tiene que estar al principio de tu código" no es que literalmente tenga que estar la priméra línea de tu script .. sino -antes- de cualquier HTML/javascript .. un espacio .. etc y en general "salida" que puedas haber generado.
Recuerda como funciona PHP .. PHP genera la "página" que será entregada al cliente (navegador).
También hay que aclarar que si tu en tu código en algún punto haces un "header(Location ...)" supuestamente es por qué quieres deterne la ejecución del script en ese punto y mandar a "llamar" a otro script indicandole al cliente (navegador) que cambie la página que está viendo por otra vía cabeceras HTTP (más rápido y transparente que por ejemplo haber "generado" ese HTML o javascript para redireccionar).
En definitiva .. comprender que hace "header()" va mas allá de saber la descripción de la función en si. Hay que conocer que todo esto se basa en otros conceptos como el "protocolo HTTP" y como funciona todo esto de una comunicación "cliente-servidor" bajo este protocolo. Se que esto será muy teórico para algunos .. pesado y tal vez aburrido .. pero, no quiere decir que se aprenda de memoria uno el protocolo HTTP sino de saber como va el "cuento" .. Cualquier duda al respecto .. consulten. (aunque no es un tema própio de PHP .. pero si trabajamos con "PHP" en este médio: "para la web" es necesario conocerlo).
Un saludo,