He was first labelled "Heart of the Tiger" during WC1 (probably the Secret Missions). We presumably first found out about it in WC2 (if that bit was included in WC2's manual, as it was in KSaga). WC2 KSaga, at any rate, features a letter from Prince Thrakhath (dated 2655.200), which mentions this name.
The name, btw, is just a title of respect that the low-born Kilrathi have for Blair. While Hobbes' personality key also used this name, one must be sure to get the relationship right. The key used the name because it had been given to Blair - not vice versa.