The above answers are correct in that you need an anchor tag in your HTML, but how that plays out depends entirely on what the image is that you are linking.
I don't see any reason to ever have an empty anchor tag. That's meaningless. Most likely you are either linking a logo or wordmark or site title or some combination. That should go in your HTML code, even if you plan to replace it with an image.
The first consideration is whether your header image itself is content or design. In the case of logos, it sometimes is content. In the case of site titles or wordmarks I would more often say the image is simply design, and the text is content.
For an image that is content in it's own right:
<div id="header">
<a href="/"><img src="logo.png" alt="My company"></a>
<!-- navigation START -->
<ul id="main_navigation">
For an image that is replacing content:
<div id="header">
<h1><a href="/">My Company</a></h1>
<!-- navigation START -->
<ul id="main_navigation">
and style:
#header h1 a {
display: block;
text-indent: -999em;
height: ??px;
background-image: url(path/to/image.png);
}
In either case, you have given semantic meaning to the area used as a link. I can't quite imagine a situation where you would want a meaningless link.