Kaikki alkoi siitä kun Michael Bond osti viime hetkellä teddy-karhun vaimolleen Brendalle joululahjaksi v. 1956. He nimesivät karhun Paddingtoniksi, koska asuivat silloin lähellä kyseistä Lontoon rautatieasemaa. Omaksi huvikseen Bond alkoi kirjoitaa tarinaa kyseisestä nallesta ja pian hän huomasi, että hänellä oli kokonainen kirja valmiina julkaistavaksi. "A Bear Called Paddington" julkaistiin v. 1958 ja sen miellyttävät kuvitukset olivat Peggy Fortnumin käsialaa.

Tämän jälkeen on ilmestynyt useampiakin Paddington-kirjoja Michael Bondin kirjoittamana ja Peggy Fortnumin kuvittamana. Karhuherra Paddingtonista on myös tehty televisiosarjoja.

Tarina alkaa siitä kun herrasväki Brown ovat Paddingtonin asemalla ja siellä löytävät yksinäisen karhun postisäkkien takaa kadonneet-osastolla. Tällä karhulla oli lappu kaulan ympärillä jossa luki "Olkaa ystävällisiä ja huolehtikaa tästä karhusta". Herra ja rouva Brown päättävät antaa Paddingtonin asua luonaan ja Karhuherra Paddington adoptoidaan Brown-perheen karhulapseksi.

Karhuherra Paddingtonin huolehtimisesta muodostui varsinainen tehtävä. Paddington oli hyväluontoinen ja halusi auttaa uutta perhettään miten vain taitoi, mutta hänen utelias luonteensa ja kömpelyys aiheutti usein sen, että jopa yksinkertaisimman tehtävän lopputuloksena oli täydellinen katastrofi.