HTML list menu to WordPress menu

I have purchased an HTML theme that I want to rebuild into WordPress.
I’m having trouble making the menu work.

Beneath is the HTML for the menu. (without the beginning and end of the UL).

<li class="menu-level-0"><a href="portfolio-cols3.html"><i class="icon-menu icon-menu1"></i><span>Portfolio</span></a>
                <ul class="submenu-1">
                    <li class="menu-level-1"><a href="portfolio-cols3.html"><span>Three Columns</span></a></li>
                    <li class="menu-level-1"><a href="portfolio-cols4.html"><span>Four Columns</span></a></li>
                </ul>
            </li>

            <li class="menu-level-0 current-menu-item"><a href="#"><i class="icon-menu icon-menu2"></i><span>Pages</span></a>
                <ul class="submenu-1">
                    <li class="menu-level-1"><a href="about-us.html"><span>About Page</span></a></li>
                    <li class="menu-level-1"><a href="pricing.html"><span>Pricing Page</span></a></li>
                    <li class="menu-level-1 current-menu-item parent"><a href="index.html"><span>Home Pages</span></a>
                        <ul class="submenu-2">
                            <li class="menu-level-2 current-menu-item"><a href="index.html"><span>Gallery images</span></a></li>
                            <li class="menu-level-2"><a href="index-2.html"><span>OneByOne Slider</span></a></li>
                            <li class="menu-level-2"><a href="index-3.html"><span>Video in header</span></a></li>
                            <li class="menu-level-2"><a href="index-4.html"><span>Image &amp; Video Slider</span></a></li>
                        </ul>
                    </li>
                    <li class="menu-level-1 parent"><a href="services-2.html"><span>Services Page</span></a>
                        <ul class="submenu-2">
                            <li class="menu-level-2"><a href="services-2.html"><span>Services Page (var1)</span></a></li>
                            <li class="menu-level-2"><a href="services.html"><span>Services Page (var2)</span></a></li>
                        </ul>
                    </li>
                    <li class="menu-level-1"><a href="blog.html"><span>Sidebar Right</span></a></li>
                    <li class="menu-level-1"><a href="blog-sidebar-left.html"><span>Sidebar Left</span></a></li>
                    <li class="menu-level-1 parent"><a href="#"><span>Shortcodes</span></a>
                        <ul class="submenu-2">                              
                            <li class="menu-level-2"><a href="shortcodes-buttons.html"><span>Buttons &amp; Lists</span></a></li> 
                            <li class="menu-level-2"><a href="shortcodes-text.html"><span>Text &amp; Images</span></a></li>
                            <li class="menu-level-2"><a href="shortcodes-charts.html"><span>Charts</span></a></li>  
                            <li class="menu-level-2"><a href="shortcodes-columns.html"><span>Columns</span></a></li>
                            <li class="menu-level-2"><a href="shortcodes-columns-full.html"><span>Columns full width</span></a></li>
                            <li class="menu-level-2"><a href="shortcodes-lightbox.html"><span>Lightbox</span></a></li>
                            <li class="menu-level-2"><a href="shortcodes-media.html"><span>Videos &amp; Galleries</span></a></li>
                            <li class="menu-level-2"><a href="shortcodes-maps.html"><span>Google Maps</span></a></li>
                            <li class="menu-level-2"><a href="shortcodes-tabs.html"><span>Tabs &amp; Toggles</span></a></li>
                            <li class="menu-level-2"><a href="shortcodes-tables.html"><span>Boxes &amp; Tables</span></a></li>                            
                            <li class="menu-level-2"><a href="shortcodes-typography.html"><span>Typography</span></a></li>
                            <li class="menu-level-2"><a href="shortcodes-widgets.html"><span>Custom Widgets</span></a></li>
                        </ul>
                    </li>
                </ul>
            </li>
            <li class="menu-level-0"><a href="blog.html"><i class="icon-menu icon-menu3"></i><span>Blog</span></a></li>
            <li class="menu-level-0"><a href="contact.html"><i class="icon-menu icon-menu4"></i><span>Contact</span></a></li>

I need to get the HTML returned by wp_nav_menu() look like the code above in order to get the menu the correct way in the template.

How should I do this?