I remember it as "He travelled through Old England and the most part of Wales", but I got it from listening to a singer in a folk club, so perhaps that's not the original.

Don T.