It should be accessible in any org where the SOAP API is enabled. For professional edition orgs this would mean either buying the API add-on packbuying the API add-on pack or being part of a managed application with a special ClientId token that allows it to invoke the API.
If you have a PE org with the API add-on I'd contact support since I believe it's possible for the REST API to be disabled per-org and there might be some historical reason it's not enabled that support can fix via black tab.