I've a domain name with network solutions, which includes an email service too.

What I need to do is to host my domain name with a webhost company other than network solutions, and keep my e-mail service with network solutions. What sould I do in this case?

Thanks

You could move your domain to a company that allows you to modify the DNS and point the MX to network solutions.

Get the MX entry for your domain pointed to the mail servers at Network Solutions.