From time to time I need to remove all history from a GitHub repository, for instance right before releasing a package I've worked on in private. Sometimes I don't want people to see all mistakes I've made along the way :-).

Here are the steps I perform:

# clone the repo (skip if you already have a cloned repo locally)
git clone git@github.com:USERNAME/REPOSITORY.git
cd REPOSITORY

# remove all history locally
rm -rf .git

# create a new local repo
git init

# add everything
git add .
git commit -m "First commit"

# nuke history on GitHub (irreversable)
git remote add origin git@github.com:USERNAME/REPOSITORY.git
git push -u --force origin master

That -u flag will automatically set tracking. That --force option will make GitHub accept your push even though the history of the repo they have is unrelated to the empty history that is being pushed.

Be aware that this will also close all PRs. Any links to specific comments you might have will not work anymore. If you're working on the repo with other people, inform that history has been deleted (or even better, ask them if it's ok to delete the history before you do that), they will have clone the repo again.

UPDATE: meanwhile Bram Van Damme shared a few nice, shorter, alternatives to achieve the same goal.