Don't do it where the shortcuts/tabs are. You are effectively 'right-clicking'. Do this at the top of the Safari window either side of where it has the page title (but don't click on the title or it'll give browsing history).
I assume you know how to use the touch pad and key to get the 'right-click' menus up? If so, you are looking for the 'Customize Toolbar...' menu.