A while back Okta changed the provisioning credentials for salesforce.com from the old username and password+token approach to using OAuth. Whilst the new approach was added to the Okta help documentation (https://help.okta.com/oie/en-us/Content/Topics/Provisioning/Salesforce/sfdc-configure-provisioning-REST.htm), the need for the documents to cover both the old and new can lead to some confusion. A customer hit a snag and I ran through the setup procedure in my own tenant.
The following article covers the notes and screen shots from setting up provisioning to salesforce.com with OAuth. The comments should be used in concert with the product docs (not instead of).
The relevant steps are in https://help.okta.com/en-us/Content/Topics/Provisioning/Salesforce/sfdc-configure-provisioning-REST.htm (and link to other pages). The steps referenced below are as per this documentation. First two steps are “Prerequisites” in https://help.okta.com/en-us/Content/Topics/Provisioning/Salesforce/sfdc-enable-provisioning.htm.
Prerequisite Steps
Step 1 – Create admin account in SFDC (normal system admin will work if you’re setting up a test or demonstration environment)
Step 2 – Create custom user profile (SFDC – ADMINISTRATION > Users > Profiles) to setup a set of permissions for the account connecting to SFDC can perform. Note that if you are using the system admin account you will not need a custom user profile.
Setup Connected App and Get OAuth Credentials
Step 3 – Create connected app for the Okta connection.

Step 4 – You might need to wait as directed (you won’t get a prompt) before,
Step 5 – Go get the API Key and Secret


We will come back to Step 6 at the end. For now, go to the steps under Configure OAuth and REST integration.
Configure OAuth and REST Integration
Step 1 – Go to the SFDC app provisioning page in Okta.
Step 2 – Enable provisioning and Copy both Key and Secret values from the SFDC page into the relevant fields in the Okta SFDC app provisioning page.
Step 3 – Click the Authenticate button (in my system it was Re-authenticate as I’d already had values).

Step 4 – When prompted re-authenticate to SFDC as the admin account (there may be a MFA challenge with a PIN sent to the email address for the app).
Step 5 – Approve the OAuth scopes

Step 6 – You should see a success message and can Save the settings

Check Refresh Token Policy
This is the last step skipped above. Go back into SFDC and find the new connected app. I found the App Manager view easiest. Click the Manage function.

Check the Refresh Token Policy.

That should be it. You should be able to provision to SFDC from Okta.
This concludes the article.
Hey David, just to add: If you have problems enabling provisioning with Salesforce: Make sure that you use either a Dev or Prod instance. With a Trial (30days) afaik Provisioning in Salesforce is not possible – did give some people already some headaches.