Paljud inimesed vaatavad puudleid ja mõtlevad "froufrou", kuigi tegelikult kasvatati puudlit töötava talukoerana. Puudli tausta paremaks mõistmiseks on siin tõu alguse ajalugu.
Kõik koerad põlvnevad hundist, mis võib seletada, miks nad sireenide ja muu taolise peale uluvad. Algne koer kodustati 13 000–17 000 aastat tagasi. Alates nendest algusaegadest on inimene loonud üle 300 tõu, alates pisikestest chihuahuadest ja Yorkshire terjeritest kuni hiiglaslike dogide, iiri hundikoerte ja karvaste newfoundlandi koerteni. Iga tõug töötati välja kindlat eesmärki silmas pidades, alates inimese süles istumisest ja kaaslaseks olemisest kuni kariloomade ja vara valvamiseni kuni langenud ulukite kättesaamiseni.
Aja möödudes hakkasid inimesed ootama, et koerad saaksid teha rohkem kui nende põhiülesanne, sest lihtsam ja odavam on lasta ühel koeral teha mitut tööd kui omada iga ülesande jaoks eraldi koera. Näiteks puudel aretati ulukite küttimiseks ja väljatoomiseks ning selleks, et tal oleks instinkt karja karjatamiseks.
Millal ja kus puudl eraldi tõuna tekkis, on raske öelda. Roomlased nikerdasid haudadele puudlitaolisi koeri juba 30. aastal pKr ning neid kujutati Kreeka ja Rooma müntidel, kuid eksperdid ei tea, kas need koerad surid välja või arenesid neist edasi tänapäevane puudlik.
Puudleid nimetatakse mõnikord "prantsuse puudliteks", kuid tõugu peetakse üldiselt sakslasteks, kuigi selle tegelik päritoluriik on ebaselge. Kaasaegsele puudlile andsid oma panuse Venemaalt ja Prantsusmaalt pärit koerad ning üks teooria väidab, et puudli esivanemad pärinesid Portugalist või Hispaaniast.