Um genau zu sein ist "div" auch nicht die "Lösung". Das <div>-Element ist ein semantisch bedeutungsfreies Element, welches nur zum Gruppieren von Elementen dient. Wenn man HTML4 oder XHTML verwendet, kann man es durchaus zum Umschließen von Elementen verwenden, die den Header der Seite repräsentieren sollen. Wenn man HTML5 verwendet sollte man dagegen das <header>-Element nutzen, welches genau für diesen Zweck gedacht ist.
In jedem Fall ist die Lösung für deinen Wunsch ein Blockelement, welches dein Menü und das Logo umgeben kann - also ein <div> oder <header>, je nachdem welchem HTML-Standard Du folgst.
Der Königsweg wäre der Verzicht auf das <div> an der Stelle, was aber nur möglich ist wenn Du deinen Header entsprechend sparsam gestalten willst.