Mahler wrote his first six part version of the Songs of a Wayfarer with piano accompaniment in 1884. The final orchestral version which consists of four movements was only written twelve years later. In the meantime, Mahler had written a number of important works, including the First Symphony, two movements of which feature material from these songs.

Mahler himself assembled the texts for the songs based on the collection of folk poems so beloved by the German Romantics, Des Knaben Wunderhorn. This anthology was prepared by Achim von Arnim and Clemens Brentano and published in 1805 and was one of Mahler's favourites – he drew on it for numerous of his songs. The moods of these verses in many respect resemble the poems of Wilhelm Müller, which Schubert immortalised in his song cycles Die Schöne Müllerin and Winterreise. It is hardly coincidental that in the fourth Mahler song, we find a characteristic Schubertian musical motif: the “wandering” theme, both in its major and minor forms, just as we encounter it in the twentieth song of Winterreise.