Did you check to make sure someone didn't delete the Workflow Task List?  But regardless in the Workflow Settings you can create a new one.  In the drop down where you set the list, select the option "Create new...", then type in a name for your new workflow task list. 

That's exactly what happened, not sure how, turned out it wasn't in the Recycle Bin either. In case anyone is wondering in the future, yes if your workflow task list is deleted, you can take the "Workflow Task List" from another site, template it out, and then add that list to your current site and it will work with the Nintex workflows without any further setup. 

Did you look in the site collection recycle bin?  If you didn't delete it, you wouldn't see it in the normal recycle bin.  You'd need to go up to the site collection bin to see it.  

Did the "Create new" option from the Workflow settings not work?  You can create multiple workflow task lists on a site if you want.  The default one is just what get's created when you enable the Nintex Workflow Feature.  You could also turn off the feature, and turn it back on and it will create a new task list.