I deleted .bash_history, now history isn't saved anymore (although I re-created it)

I encountered the same problem after willingly deleting the .bash_history file.

The simple solution is to not only touch the file but also add some text - one or several line feeds are not sufficient:

echo "exit" >> ~/.bash_history

Then completely quit Terminal and reopen it. If you've saved all your work in all terminal sessions, you can also just

killall Terminal

Update:

I tried to replicate your environment in a 10.11 VM and it's indeed a problem with RVM: commenting out all rvm related lines in .profile and .bash_profile re-enables updates of the .bash_history file.

The .bash_logout file method (with the content shell_session_update) seems to work reliably here though. Just remember to always enter exit before closing a Terminal window or quitting Terminal. Without entering exit the history won't be updated.