That's the right answer, assuming you're using POP3. If that doesn't work, there may be an issue with the way the server handles its POP requests (e.g. GMail does the opposite -- in spite being told to delete messages, it completely ignores this request).
Note that if you have IMAP, you don't see that option, and I'm not really sure that there is any way to do that. The model of IMAP is that your inbox is held on the server and that you act on the server copy of the inbox whenever you make a change. Any e-mail stays on the server as long as it's in a server folder such as the inbox, but if it gets moved out, it happens on the server too.