You can do it anytime after you get the airship. To do that you need at least to have defeated Lich and gotten the Float stone.
There's a chain of islands between the northern two continents. On one of them there's a cave that will lead you to Bahamut. He'll tell you to get a symbol of courage (or something like that) from a castle on the Western side of the North-Eastern continent. There's a castle around that area, but the only way to get there is by landing the airship pretty far away on a peninsula just north of the castle and walk the rest of the way. Go through it (The second floor is annoying) and find the "Tail", which you'll trek back to your airship with, give to Bahamut, and upgrade classes.
I should probably mention the whole thing is an optional quest so you'll miss it if you don't explore.