How do I make Bash history undeleteable?

What you ask can be done with ...

sudo chattr +a ~$USER/.bash_history
sudo chattr +i ~$USER/.profile

This will set the "append only" for .bash_history and "immutable bit" for .profile and even root can not delete or truncate the file unless that bit is removed. The 2nd command prevents the user from editing the settings for .profile.

Next put this in /etc/bash.bashrc or /etc/.profile:

# #Prevent unset of histfile, /etc/profile
HISTFILE=~/.bash_history
HISTSIZE=10000
HISTFILESIZE=999999
# Don't let the users enter commands that are ignored# in the history file
HISTIGNORE=""
HISTCONTROL=""
readonly HISTFILE
readonly HISTSIZE
readonly HISTFILESIZE
readonly HISTIGNORE
readonly HISTCONTROL
export HISTFILE HISTSIZE HISTFILESIZE HISTIGNORE HISTCONTROL

That will lock down most simple actions a user could make to mess this up. But it wont stop the more experienced users ...

a user can simply switch to another shell and you wont see anything register.
anyone with the admin password or any process with CAP_LINUX_IMMUTABLE capability can remove the immutable bit
commands that start with a space by default are not stored in history.
you can not stop a kill -9 $$. That command will prevent writing to history.

So what you ask is rather pointless. If you do not trust your users do not let them on your system.

If this question was created to tract actions by hackers... you can totally forget about this; they are not likely to use bash when they are on your system and this history only works with bash.

A far superior option would be to use grsecurity or to install acct (The GNU Accounting Utilities).

This is not the answer you were looking for, but what you really want is linux's audit system, not bash. The audit system is designed expressly for things like this, whereas shell history is a convenience feature and there are many ways to modify it or simply not use it, as stated in many answers above.

You cannot protect the .bash_history file from getting deleted. If you make its permission bits read-only, bash will fail to write in it.

However, you can create an alias for rm in your ~/.bashrc so that, every time you want to delete something, it will ask you (y/n) questions

Put this line in your ~/.bashrc file.