For this and similar cases, Gmail has a handy shortcut down its More Actions ... menu. You can create a new label on the spot.
Create Labels As and When You Need Them in Gmail
To create new labels in Gmail just as you need them:
- Click the Labels drop-down menu with the message or messages you want to label checked or open.
- Select Create new.
- Type the desired label name under Please enter a new label name:.
- Click OK.

