When using wp_nav_menu
you can pass arguments to it which help you style the output, look at:
$container
Whether to wrap the ul, and what to wrap it with. Allowed
tags are div and nav. Use false for no container e.g. container =>
false .$container_class
the class that is applied to the container.$container_id
The ID that is applied to the container.$menu_class
CSS class to use for the containing div element which
forms the default menu, or the ul element when a custom menu is
configured in the admin interface.$before
Output text before the of the link.$after
Output text after the of the link.$link_before
Output text before the link text.$link_after
Output text after the link text.$items_wrap
Whatever to wrap the items with an ul, and how to wrap
them with.
So in you case you can use
array( 'link_before' => '<div class="your_class">' , 'link_after' => '</div>');
But if you ask me you can probably do what you want with the classes WordPress prints out anyway.