When using wp_nav_menu you can pass arguments to it which help you style the output, look at:
$containerWhether 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_classthe class that is applied to the container.$container_idThe ID that is applied to the container.$menu_classCSS 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.$beforeOutput text before the of the link.$afterOutput text after the of the link.$link_beforeOutput text before the link text.$link_afterOutput text after the link text.$items_wrapWhatever 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.