Yes, it's correct and sounds very natural.
It can be interpreted in two ways.
It can be literal. For example, if you are in a building, anywhere but the ground floor or basement, someone could introduce you to a man saying 'Have you met Tom?' and you could answer 'Yes, I met him on the way up'. This might mean that you met him in the elevator or on the stairs as you were making your way upstairs.
Figuratively, if you are at the peak of your career, it could mean that he was a friend or acquaintance whom you met while you were on your way to becoming successful.