Git says local branch is behind remote branch, but it's not

Scenario:

1. I make a new branch
   
2. hack on it
   
3. commit it
   
4. push it
   
5. hack on it some more
   
6. commit again
   
7. try to push again
   

Git responds:

> Updates were rejected because the tip of your current branch is behind its remote counterpart. etc.

I'm the only one hacking on this branch - no one else is touching it. The remote branch is actually behind the local branch. I shouldn't have to pull at all.

(And if I do pull, Git reports conflicts between the two, and forces me to merge the branch into itself)

Why is this (likely) happening? And how can I diagnose/fix it?

To be clear, I'm not branching anywhere, and no one else is working on it:

Remote: Commit A -------- Commit B  

Local:  Commit A -------- Commit B -------- Commit C  

C is a straight continuation of B, no branching involved. But git thinks C is a branch of A:

Remote: Commit A -------- Commit B  
  
                  ------- Commit C  
                /  
Local:  Commit A -------- Commit B  

It's not; it's a straight continuation of B.

You probably did some history rewriting? Your local branch diverged from the one on the server. Run this command to get a better understanding of what happened:

gitk HEAD @{u}

I would strongly recommend you try to understand where this error is coming from. To fix it, simply run:

git push -f

The -f makes this a “forced push” and overwrites the branch on the server. That is very dangerous when you are working in team. But since you are on your own and sure that your local state is correct this should be fine. You risk losing commit history if that is not the case.

The solution is very simple and worked for me.

Try this :

git pull --rebase <url>

then

git push -u origin master

This happened to me when I was trying to push the develop branch (I am using git flow). Someone had push updates to master. to fix it I did:

git co master
git pull

Which fetched those changes. Then,

git co develop
git pull

Which didn't do anything. I think the develop branch already pushed despite the error message. Everything is up to date now and no errors.

To diagnose it, follow this answer.

But to fix it, knowing you are the only one changing it, do:
1 - backup your project (I did only the files on git, ./src folder)
2 - git pull
3 - restore you backup over the many "messed" files (with merge indicators)

I tried git pull -s recursive -X ours but didnt work the way I wanted, it could be an option tho, but backup first!!!

Make sure the differences/changes (at git gui) are none. This is my case, there is nothing to merge at all, but github keeps saying I should merge...