A menos que imprimas algo, exista HTML o algún espacio antes de usar header() no deberías tener problemas, sin embargo nos es complicado adivinar si ese es todo el código que usas.
De igual forma si no tienes activado el reporte de errores jamás te vas a enterar de un posible error.
O ver si obtienes algo así:
PHP:¿Por qué me sale "Warning: Cannot modify header information - headers already sent by (output started at 1:2) in 3 on line 4"?