It is common to run Fish shell in multiple terminals at the same time. When used this way, the command history of one terminal session is not available in Fish running in a second terminal. This is because Fish does not want to update the common history file at the end of every command. This might be for performance and to avoid race conditions.
When you want the command you used in another terminal running Fish, just explicitly ask Fish in the current terminal to merge the history of all open sessions:
$ history --merge
Tried with: Fish 2.2.0 and Ubuntu 14.04