The error message does not mean that the header() function must be the first line of code. It just has to be executed before any output is sent (to the browser). Output is sent when you call echo, print() or other functions that send information. If an error occurs and error_reporting is on, errors are sent to the browser. Anything, ANYTHING including blank lines or spaces that are outside of the php tags (<?php ... ?> or <? ... ?>) is automatically sent to the browser.
Check everything above the code that is calling the header() function. Also check all included files. One common cause is when there is a line-feed (or carriage-return) after the last closing tag "?>" in an included file. A common solution to this, is to just not include the closing tag in the included files. You'll have to decide for yourself whether that is a hack or not.
Also make sure there is NOTHING BEFORE the first opening php tag.