Tienes dos opciones:
1.Puedes poner antes que nada en tu código:
Código PHP:
<?
ob_start();?>
Y al final
Código PHP:
<?
ob_en_flush();
?>
2- No haber enviado nada a tu navegador antes del header
Lo más recomendable y consume menos recursos es no enviar nada al navegador, pero ambas opciones son posibles...
Salu2 ;)