How do I add a parent commit before all other commits in Git?

Something like this should work.

# Create a new branch with the old history
$ git checkout --orphan old-history    
$ git add <old-files>
$ git commit

# Rebase master on top of the branch with old-history
$ git checkout master
$ git pull --rebase . old-history

There are instructions in the git-filter-branch(1) man page for this:

   To set a commit (which typically is at the tip of another history) to be
   the parent of the current initial commit, in order to paste the other
   history behind the current history:

       git filter-branch --parent-filter 'sed "s/^\$/-p <graft-id>/"' HEAD

   (if the parent string is empty - which happens when we are dealing with
   the initial commit - add graftcommit as a parent). Note that this assumes
   history with a single root (that is, no merge without common ancestors
   happened).

Taking a suggestion from Kent, you might want to add --tag-name-filter cat to this command to rewrite tag names to the new commits. This is also documented in the man page, with a warning to back up the old tags first:

       The original tags are not deleted, but can be overwritten; use
       "--tag-name-filter cat" to simply update the tags. In this case, be
       very careful and make sure you have the old tags backed up in case
       the conversion has run afoul.

The man page also explains why signatures must be stripped when rewriting tags:

       Nearly proper rewriting of tag objects is supported. If the tag has
       a message attached, a new tag object will be created with the same
       message, author, and timestamp. If the tag has a signature
       attached, the signature will be stripped. It is by definition
       impossible to preserve signatures. The reason this is "nearly"
       proper, is because ideally if the tag did not change (points to the
       same object, has the same name, etc.) it should retain any
       signature. That is not the case, signatures will always be removed,
       buyer beware. There is also no support for changing the author or
       timestamp (or the tag message for that matter). Tags which point to
       other tags will be rewritten to point to the underlying commit.

After the single-root example, the man page continues with multiple-root instructions:

   If this is not the case, use:

       git filter-branch --parent-filter \
               'test $GIT_COMMIT = <commit-id> && echo "-p <graft-id>" || cat' HEAD

   or even simpler:

       git replace --graft $commit-id $graft-id
       git filter-branch $graft-id..HEAD

Using git filter-branch is much cleaner than using git --rebase, which functions like a combination of diff and patch, applying the changes in each commit on top of another one. Instead, git filter-branch leaves the actual files in each commit untouched and changes the parent commit pointer directly.

Of course, the new commits will have different SHAs than the original ones – that is unavoidable since the parent commit is included in the SHA calculation.

---

You could also try Mark Lodato's git-reparent script, which appears to use git plumbing commands to achieve a similar result.