At first, rename the local branch, then the remote branch.
Renaming the local branch:
If logged in another branch,
git branch -m old_branch new_branch
If logged in the same branch,
git branch -m new_branch
Renaming remote branch:
git push origin: old_branch
git push --set-upstream origin new_branch
Also, check out this Git Tutorial to know more.