Did you ever sync contacts from iTunes? Perhaps they're still there?
If your contacts were ever "just on your phone" then (a) you must not have had Contacts enabled in iCloud or any other email account, then (b) at some point you enabled Contacts with your iCloud account, which would send new contacts to iCloud.
When (b) happens it is not clear what happens to the contacts that were already on your iPhone. Maybe they continue to reside only on your iPhone until something triggers your iPhone to recognize that only iCloud contacts should be used, Apple is not really clear on this fine point.
While contacts resided only on your iPhone, they would have been part of your iPhone backup. Normally contacts aren't part of your backup because they're somewhere in the cloud (iCloud, Gmail, etc.) but locally-saved items are in a backup. The trouble is, have you backed up your iPhone since your contacts went missing? If so, they may be toast. If not, then you might try restoring your iPhone to your last backup. This may recover them, it depends on when you turned on iCloud Contacts. Restoring to a backup may recover things, but you lose anything that happened on your iPhone that happened since then.
Unfortunately there's only one way I know of backup the current state of your iPhone as it is now and preserve your old backup. You'd have to be backing up to iTunes, not iCloud, and you'd go into iTunes and archive the old backup. Then perform a new backup which should not overwrite the archived one. Now restore to the archived one to get the contacts back (if they're there) and export them off your iPhone using a 3rd party app ... turning on a cloud service like iCloud may not force them to sync to iCloud. You could then restore your iPhone again to the newer backup you made to recover anything since the archived backup was made. Very complicated, I know ... but I don't know how else to recover your old contacts if they were only on your iPhone.