I recently received a frantic email from a friend testing an upgrade from CRM 4 to 2015. He was testing workflows, and they did not appear to be working, as the completed workflows did not appear in the workflow history for the record.
It turns out that they were working, but when we had upgraded the environment, we changed some of the workflows to be real time. When you do this, the workflow no longer appears in the system jobs or workflow history. The workflows were actually running.
To test the success of the workflow, check for the desired outcome. Also, a real time workflow that runs on create of a record will typically throw an error when saving the record.