This happens if you initialized a new github repo with
git remote add origin [//your github url]
//pull those changes
git pull origin master
// or optionally, 'git pull origin master --allow-unrelated-histories' if you have initialized repo in github and also committed locally
//now, push your work to your new repo
git push origin master
Now you will be able to push your repository to github. Basically, you have to merge those new initialized files with your work.
git pull fetches and merges for you. You can also fetch and merge if that suits you.