It depends entirely on the type of phone you have. If you have an Android phone, your contacts should be backed up on your Gmail account, so you might try logging in on a computer terminal and seeing if they are there. There are similar backup utilities for iOS, and even Blackberry and WebOS!
If you have a regular cellphone, you're probably out of luck; you would know if you were enrolled in a backup service offered by your carrier. If you aren't, you might check with a local repair center if you've been to one recently, to see if they have your contacts backed up from any service work they performed.
Short of this, you could use an old/spare phone that you used to use to recover most of your contacts, since they would still be on that old phone. And lastly, log into your account on the cell provider's website, and you should at least be able to see a detailed call history - and recover the actual phone numbers from there!