If you have them associated with iCloud, go to Settings-iCloud and then turn OFF Contacts. You will be asked the following question: "What would you like to do with the previously synced iCloud contacts on your iPhone?". Your choices will be:
1. Keep on my iPhone
2. Delete from my iPhone
3. Cancel
The procedure is similar with contacts associated with other services.
If your contacts are not associated with an email service then you will have to use the iTunes app on your computer to mass delete, if I'm not mistaken. Other than that, you will have to delete them one by one on your iPhone.