The first thing you must to do is create a new repo on GitHub. Do not create it with any file (README, license or gitignore). We can add these files after.

So go ahead:

% echo "# Test project" > README.md
% git init
Initialized empty Git repository in /Users/example/Projects/example/.git/
% git add .
% git commit -m "First commit"
[master (root-commit) 1ca06ac] First commit
 1 file changed, 1 insertion(+)
 create mode 100644 README.md
% git remote add origin git@github.com:<YOUR_USER>/test-project.git
% git remote -v
origin	git@github.com:<YOUR_USER>/test-project.git (fetch)
origin	git@github.com:<YOUR_USER>/test-project.git (push)
% git push -u origin master
Enumerating objects: 3, done.
Counting objects: 100% (3/3), done.
Writing objects: 100% (3/3), 895 bytes | 895.00 KiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To github.com:<YOUR_USER>/test-project.git
 * [new branch]      master -> master
Branch 'master' set up to track remote branch 'master' from 'origin'.