Erro ao executar push no repositório remoto | Git: Controle e compartilhe seu código

Criei o repositório local e remoto com sucesso.

Tentei executar o push usando tanto

git push origin master

como

git push -u origin master

Ocorre o mesmo erro:

$ git push -u origin master
To https://github.com/caetanoc/curso-git.git
 ! [rejected]        master -> master (non-fast-forward)
error: failed to push some refs to 'https://github.com/caetanoc/curso-git.git'
hint: Updates were rejected because the tip of your current branch is behind
hint: its remote counterpart. Integrate the remote changes (e.g.
hint: 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.

Obrigado!