V průběhu let se sestava skupiny poměrně často obměňovala. Zejména roky 1974 a 1979 byly pro Poutníky zlomové, neboť do kapely zavítali tři velcí muzikanti, a to Zdeněk Kalina, Robert Křesťan a v neposlední řadě i mandolinista Pavel Petržela.

První deska Poutníkům vyšla v roce 1987. Sestavu tehdy tvořili kapelník a kytarista František Linhárek, skladatel a zpěvák Robert Křesťan, banjista, houslista a saxofonista Luboš Malina, zpěvák a kytarista Zdeněk Kalina, mandolinista Jiří Plocek, kytarista Mirek Hulán, kontrabasista a zpěvák Jiří Pola a konferenciér Josef Prudil. V této sestavě Poutníci vydali celkem pět desek a navštívili spoustu zemí Evropy. Dvakrát dokonce ve Spojených státech získali ocenění za nejlepší neamerické album roku. Kromě toho kapela odehrála stovky koncertů v tehdejším Československu.

V létě 1991 František Linhárek kapelu opustil, aby se nadále věnoval pouze manažerské činnosti. Na postu kapelníka ho proto vystřídal Mirek Hulán. Poprvé v historii Poutníků také do kapely přibyla zpěvačka, kterou se stala se Hana Černohorská.

Od podzimu 1997 v kapele začal působit mandolinista a houslista Jan Máca, který je pokládán za jednoho z nejtalentovanějších muzikantů českého bluegrassu v 90. letech. Skupina, v jejíž sestavě se snoubila energie mládí s uměleckými zkušenostmi, začala vystupovat v televizi a okupovat vlny rozhlasových stanic.

Od začátku třetího tisíciletí v kapele došlo k dalším personálním změnám. V říjnu roku 2001 Poutníky opustil dlouholetý sólový kytarista Mirek Hulán, kterého však rychle zastoupil mandolinista, houslista, kytarista a zpěvák Jirka Mach. V říjnu 2007 se Zdeněk Kalina rozhodl, že bude vystupovat pouze na důležitých koncertech a akcích, které se konají v blízkosti Brna. Stal se tak emeritním Poutníkem.

V roce 2010 jihomoravští hudebníci vyrazili na turné, které se konalo k příležitosti 40. výročí působení kapely. Vrcholem celoročních oslav se stala společná šňůra s Robertem Křesťanem a jeho Druhou trávou. Zvláštní význam měl zejména koncert, který se konal v adventním období v Brně a na kterém Poutníci pokřtili své v pořadí již třinácté album.