A Vándorlegény-dalok első, még 6 részből álló, zongorakíséretes változatát Mahler 1884-ben vetette papírra. A végső, zenekarkíséretes és 4 tételből álló verzió 12 esztendővel később készült. Időközben Mahler számos fontos művét megalkotta, köztük az első szimfóniát, amelynek két tételében is feltűnik a dalciklus zenei anyaga.
A dalok szövegét maga Mahler alakította ki, de konkrét népköltészeti minták, A fiú csodakürtje (Des Knaben Wunderhorn) című gyűjtemény versei alapján.  Ez az Achim von Arnim és Clemens Brentano által összeállított, 1805-ben publikált kötet Mahler egyik kedvenc olvasmánya volt – számos dalának szövegét innen merítette. A versek hangulatvilága sok tekintetben emlékeztet azokra a Wilhelm Müller-költeményekre, amelyek alapján Schubert komponálta híres dalciklusait, a Szép molnárlányt, illetve a Téli utazást. Aligha véletlen, hogy a negyedik Mahler-dalban egy jellegzetes schuberti zenei motívum is megjelenik: a „vándorlás” témája, mégpedig moll és dúr alakban egyaránt, ugyanúgy, ahogy a Téli utazás-ciklus huszadik dalában.