Below is a script adapted from @Zeelot 's answer. It should remove the history from all branches, not just the master branch:
for BR in $(git branch); do
git checkout $BR
git checkout --orphan ${BR}_temp
git commit -m "Initial commit"
git branch -D $BR
git branch -m $BR
done;
git gc --aggressive --prune=all
It worked for my purposes (I am not using submodules).