Quite possible. Keep in mind that the header navbar also displays the "my account", "shopping cart" and "checkout" links when appropriate, and "search" when activated in admin.
Depending on exactly how and where you want the links to display in the sidebar, you can edit /includes/templates/your_template/common/tpl_header.php to copy the code block beginning with <!--bof navigation display--> and ending with <!--eof navigation display--> to another file, adjust it for vertical display (mostly by adding <br /> tags between the items), and once it is working correctly delete it from tpl_header.php.
You might move the code to column_left.php or column_right.php, or to one of the regular sideboxes, or if you want it in a sidebox all to itself you can download the "blank sidebox" mod to hold it.
The logo will then automatically move to the top.
Another thought - would it work for the header nav to be below the logo (horizontal)? That would be a trivially easy edit, if it would look right for your layout.