El problema no es donde va, sino
cuándo va...
El mismo manual de referencia de PHP te lo dice muy claramente:
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.
O sea, no puedes mandar desde ese PHP
ningún echo antes de usarlo.