Remove old remote branches from Git

When I use bash autocompletion in Git, it keeps showing me branches of old remotes that I don't have anymore. When I do a git branch -la it shows those old remotes and branches while a git branch -l won't. A ls .git/refs/remotes/ also shows them. However, they are not present in my .git/config and neither are they shown when I run git remote show.

So how do I get rid of them because my autocomplete list is too long right now.

I have already tried:

git reflog expire --expire=now --all
git gc --prune=now
rm .git/refs/remotes/theoldremote
git remote prune theoldremote

I'm also aware of the fact that I can just re-clone the repo but that's just cheating ;-)

Git does not delete the (local) remote-tracking branches automatically if the branch was deleted in the remote repository. Additionally, before V2.0.1 remote-tracking branches were in some cases not deleted when you removed the remote from your git config (see VonC's answer).

To delete stale remote-tracking branches (branches that were deleted in the remote repository) for one of your remote repositories, run

git remote prune <remote>

To cite the man page or git remote:

prune

Deletes all stale tracking branches under <name>. These stale branches have already been removed from the remote repository referenced by <name>, but are still locally available in "remotes/<name>".

With --dry-run option, report what branches will be pruned, but do not actually prune them.

However, from your question it seems you manually removed .git/refs/remotes/theoldremote, so Git no longer knows about the remote repository that the remote-tracking branches belonged to. That's not how you're supposed to do it.

The normal way to remove a remote repository is to run

git remote rm <remote>

This will remove the remote from your .git/config, and will delete the remote-tracking branches.

If you just delete the directory under .git/refs/remotes/, the branches will remain behind. Then you will need to remove them manually:

git branch -rd <remote>/<branchname>

You need option -r to delete a remote branch.

I use

git push origin :remote_branch

to remove a branch from server.

git remote prune origin

to remove remote references which do not exist on server anymore

Note: while git remote prune is the answer, know that, starting with git 2.0.1 (June 25th, 2014), a git remote rm starts by removing the remote tracking branches.
So hopefully, one shouldn't have to cleanup old branches after a git remote rm.

See commit b07bdd3 by Jens Lindström (jensl)

remote rm: delete remote configuration as the last

When removing a remote, delete the remote-tracking branches before deleting the remote configuration.
This way, if the operation fails or is aborted while deleting the remote-tracking branches, the command can be rerun to complete the operation.

But if you have to, a simple git fetch can be enough, provided you have set first:

git config --global fetch.prune true
cd /path/to/repo
git config remote.origin.prune true

Push nothing to a branch to delete it:

git push remote :remote_branch

It's somewhere in the docs but it isn't really obvious.

Or did I misunderstand your question?