git submodule add fatal: Not a Git Repository

It can depends on the version of Git you are using: this recent thread (February 2012) mentions a bug:

Since recently a submodule with name <name> has its git directory in the .git/modules/<name> directory of the superproject while the work tree contains a gitfile pointing there.

When the same submodule is added on a branch where it wasn't present so far (it is not found in the .gitmodules file), the name is not initialized from the path as it should.
This leads to a wrong path entered in the gitfile when the .git/modules/<name> directory is found, as this happily uses the - now empty - name.
It then always points only a single directory up, even if we have a path deeper in the directory hierarchy.

But more generally, uses the <path> argument of git submodule:

<path> is the relative location for the cloned submodule to exist in the superproject.

• If <path> does not exist, then the submodule is created by cloning from the named URL.
• If <path> does exist and is already a valid git repository, then this is added to the changeset without cloning.
  This second form is provided to ease creating a new submodule from scratch, and presumes the user will later push the submodule to the given URL.

---

eoinoc mentions in the comments another cause, which is detailed in the question "git status returns fatal: Not a git repository but .git exists and HEAD has proper permissions".

My repo's location had changed, and I needed to update git's configuration files.

This will seem silly, but since I just wasted 30 minutes on that stupid mistake....

You parent repository must have already been created as git repository. I had just created the parent, then I created the submodule and & tried to git submodule add into the parent. However, the parent hadn't been initialized as a git repo.

This resulted in the same error as the one you mentioned ("not a git repository"). However it was the parent which wasn't a git repository.... silly.