No puedes imprimir nada antes de usar header(), consulta el manual:
http://php.net/header Cita: Recuerde que header() debe ser llamado antes de mostrar nada por pantalla, etiquetas HTML, líneas en blanco desde un fichero o desde PHP. Es un error muy común leer código con funciones como include o require, u otro tipo de funciones de acceso de ficheros que incluyen espacios o líneas en blanco que se muestran antes de llamar a la función header(). Sucede el mismo problema cuando se utiliza un solo fichero PHP/HTML.