To create a new menu here are the steps you need to follow:
Click Menus
Click Add
Enter a Name in a machine readable format which means no spaces, only letters from a-z and all text in lowercase, for example: my-menu
Click Save
Once your menu is created a block will also be created for the menu which you can use to display it on any section of your site.