! [rejected] main -> main (fetch first) followed by error: failed to push some refs — the remote branch has commits you do not have, usually because a teammate pushed after your last pull. Git will not overwrite their work. Bring their commits in with git pull --rebase (or a plain merge pull), then push again.

Do not reach for git push --force. It made the error go away in the test, and it deleted the teammate's commit from the remote branch.

The error

$ git push
To C:/.../e2/remote.git
 ! [rejected]        main -> main (fetch first)
error: failed to push some refs to 'C:/.../e2/remote.git'
hint: Updates were rejected because the remote contains work that you do not
hint: have locally. This is usually caused by another repository pushing to
hint: the same ref. If you want to integrate the remote changes, use
hint: 'git pull' before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.

The path was shortened; nothing else changed. Exit code 1.

Why it happens

A normal push may only move a remote branch forward: the commit the remote's main points at must already be in the history you send. Maria pushed Add about page after David cloned, and David then committed Add contact page on top of the old tip. His repository had never downloaded Maria's commit, so Git could not even compare the two, and the suffix (fetch first) says exactly that. Git's manual describes rejected as Git not trying to send the ref at all.

After a git fetch the same push gives the neighbouring message, because now David's repository holds Maria's commit and Git can see his branch does not contain it: 

$ git status -sb
## main...origin/main [ahead 1, behind 1]
$ git push
To C:/.../e2/remote.git
 ! [rejected]        main -> main (non-fast-forward)
error: failed to push some refs to 'C:/.../e2/remote.git'
hint: Updates were rejected because the tip of your current branch is behind
hint: its remote counterpart. If you want to integrate the remote changes,
hint: use 'git pull' before pushing again.

Same situation, same fix; only what Git knows about the remote has changed.

The fix

$ git pull --rebase
Successfully rebased and updated refs/heads/main.

$ git log --oneline --graph --all
* cdefe85 Add contact page
* 6c2aa62 Add about page
* 89da3be Add home page

$ git push
To C:/.../e2/remote.git
   6c2aa62..cdefe85  main -> main

--rebase downloads Maria's commit and replays David's unpushed commit on top of it, so the history stays a straight line and the push becomes a plain move forward. David's commit got a new id (it was 57e1c3c); that is safe because nobody else had it yet. The merge alternative, from a second round of the same race: 

$ git pull
From C:/.../e2/remote
   cdefe85..b09742a  main       -> origin/main
Merge made by the 'ort' strategy.
 prices.html | 1 +
 1 file changed, 1 insertion(+)
 create mode 100644 prices.html

$ git log --oneline --graph --all
*   8435eb2 Merge branch 'main' of C:/.../e2/remote
|\
| * b09742a Add prices page
* | 4b47462 Add opening hours
|/
* cdefe85 Add contact page

A plain git pull merged here because this Git for Windows install has pull.rebase=false in its system config (C:/Program Files/Git/etc/gitconfig). With no pull.rebase setting anywhere, the same pull stopped with fatal: Need to specify how to reconcile divergent branches.; adding --rebase or --no-rebase settles it.

How it was reproduced

Git for Windows 2.45.2 (git version 2.45.2.windows.1), run from Git Bash. One bare repository made with git init --bare played the shared remote. Maria (a fictional user) pushed the first commit, David cloned, Maria pushed a second commit, David committed and pushed: exit code 1 and the message above. The rebase pull, the merge pull and the plain-pull variant (run with GIT_CONFIG_NOSYSTEM=1) each ended in a push that succeeded. A separate run tried git push --force: the remote's main then listed only Add contact page and Add home page. The machine's personal global config was replaced by an empty file throughout.

Frequently asked

What does 'Updates were rejected because the remote contains work that you do not have locally' mean?
Someone pushed new commits to that branch after your last pull, and your repository has not downloaded them. Git refuses to replace them with your branch. Pull first, then push.
Should I use git pull --rebase or git pull to fix a rejected push?
Both work. git pull --rebase replays your unpushed commits on top of the new remote commits and keeps the history linear. A merge pull keeps your commits as they are and adds a merge commit. Teams usually pick one and stick to it.
Can I fix 'failed to push some refs' with git push --force?
Not on a shared branch. In the test, git push --force succeeded and removed the other person's commit from the remote branch; it survived only on their own machine. Pull and integrate their work instead.

More decoded errors in the Fixes category. Part 8 of the Git series, Rebase, Cherry-Pick and Stash, explains what a rebase does to your commits and why it is safe only before you push them.