exacto no puedes usar header si tienes alguna salida de texto por pantalla en algun lenguaje arriba del header, para que te funciones tiene que ser 100% php sin echo: te dejo ejemplos:
primer ejemplo:
ERROR
segundo ejemplo:
ERROR
tercer Ejemplo:
Correcto