Mnogi ljudje gledajo na pudlje in pomislijo na "froufrou", medtem ko je bil pudlec v resnici vzrejen kot delovni kmečki pes. Da bi bolje razumeli ozadje pudlja, je tukaj zgodovina začetkov pasme.
Vsi psi so potomci volka, kar lahko pojasni, zakaj zavijajo na sirene in podobno. Prvotni pes je bil udomačen pred 13.000 in 17.000 leti. Od teh zgodnjih začetkov je človek ustvaril več kot 300 pasem, od majhnih čivav in jorkširskih terierjev do velikanskih nemških dogov, irskih volčjih hrtov in kosmatih novofundlandcev. Vsaka pasma je bila razvita s posebnim namenom, od sedenja človeka v naročju in spremljevalca, do varovanja živine in premoženja do vračanja padle divjadi.
Sčasoma so ljudje začeli pričakovati, da bodo psi zmožni opravljati več kot svoje osnovne naloge, saj je lažje in ceneje imeti enega psa, ki opravlja več nalog, kot pa imeti ločenega psa za vsako nalogo. Pudelj, na primer, je bil vzrejen za lov in pridobivanje divjadi ter da bi imel nagon za čredo živine.
Kdaj in kje se je pudelj pojavil kot ločena pasma, je težko reči. Rimljani so pse, podobne pudljem, izrezljali na grobnice že leta 30 našega štetja in so bili upodobljeni na grških in rimskih kovancih, vendar strokovnjaki ne vedo, ali so ti psi izumrli ali so se nadalje razvili v sodobnega pudla.
Pudli se včasih imenujejo "francoski pudlji", vendar se pasma na splošno šteje za nemško, čeprav je njena dejanska država izvora nejasna. Psi iz Rusije in Francije so prispevali k modernemu pudlju, ena teorija pa pravi, da so pudlji predniki prišli s Portugalske ali Španije.