Esto se debe a que antes de tu función header hay salida hacia al explorador. Esto nos es posible
, tienes que eliminar cualquier tipo de salido como etiquetas <html> o echo's.
Del sitio de php.net
Cita: Remember that header() must be called before any actual output is sent, either by normal HTML tags, blank lines in a file, or from PHP. It is a very common error to read code with include(), or require(), functions, or another file access function, and have spaces or empty lines that are output before header() is called. The same problem exists when using a single PHP/HTML file.
Saludillos.