Go back in time and create branch

After the origin (or another) branch pulls, pull from that branch even if nothing changed and you should be able to delete.

The answer is in your question :

Note that I haven't made any commits yet, just branching.

If you don't commit, the changes are always kept in your working directory. Switching the branch doesn't affect your working directory, and the working directory also doesn't affect your last commit. You are seeing that the file is deleted, but the reality that it is deleted from your working directory only. If you want to clear the changes and return to the last commit use this command :

git reset --hard HEAD

So the file will be restored again.

Maybe it is not logic for you, but this behavior can be useful. Imagine that you have 2 branches : master and development, and you should always work on development before you move the changes to master. Let's say that you forgot to switch to development before starting working, then -before you commit- you realized that you are on master. The solution is simple, just switch to development then commit.