I just got the problem yesterday and solved it today, so am posting in case this might help a Windows user. For me, the problem occurred after I updated to the latest version of Git (because Visual Studio was recommending I do so-- something about things not matching.)
It turns out that I installed in the default directory Program Files, but my old Git was in Program Files (x86). (Hadn't noticed until tried reinstalling.)
Uninstalling the new version and installing the 64-bit Git for Windows Setup listed under Other Git for Windows downloads (which is not the default) overlaying the version in Program Files (x86) worked. (I tried other combinations of version and folders first.)
I did have to delete the local repository already created and restart with git init, git add ., git commit -m "first commit", git remote add origin theGitUrl (all of which worked before), before doing the git push origin master. The weird thing is that a pop-up window appeared to enter my user name and password. I didn't notice it at first and thought the processing on the git push was hung up. So, heads up about that "Other Git for Windows" version.
I did change my Environmental Variables before the fix; I don't know if that helped. I added these 2 to the PATH:
C:\Program Files (x86)\Git\bin
C:\Program Files (x86)\Git\libexec\git-core
I did this for both User and System variables.
A note on updating the PATH in Windows 10: you have to add one at a time and not include the ;