He was a musical giant; perhaps the gentlest, most generous giant one could ever meet. He was a consummate songwriter, singer and pianist, and made some excellent records under his own name.
Yet his most successful work was usually on records where his name appeared in smaller print: over the nearly six decades he was active in music, his songs were successfully covered by a huge range of artists, including Otis Redding, Glen Campbell, Boz Scaggs, The Rolling Stones, Robert Plant and Allison Krauss.
He produced top ten hits for Labelle, Dr. John and Lee Dorsey, while his arranging skills were put to use by everyone from Joe Cocker to Paul McCartney.
As the producer of The Meters and Dr. John, he was one of the original architects of what we know as funk. When Barak Obama coined the slogan 'Yes We Can!' for his successful presidential campaign, he was quoting an Allen Toussaint song.
And yet Toussaint remained a person who, as I was to discover, one could walk up to, say how much you admired their music, and receive the most gracious and humble response.
Toussaint was born and lived his whole life in New Orleans, and his music seems inseparable from that city.
Part of his genius was in the way he so easily and unself-consciously incorporated the second-line rhythms of the street parades or the horn sounds of the marching bands into his work. Listen to the arrangement he wrote for The Band's 'Life Is A Carnival' or the rolling rhythm of Aaron Neville's 'Hercules', for just a couple of random examples.
As a pianist, he seemed to have the entire history of New Orleans in his fingertips. He could quote the New Orleans classical composer Louis Moreau Gottschalk and the barrelhouse master Professor Longhair in the same phrase, yet whatever he played always had an added elegance that was all his own.
No musician has ever made me more aware of a sense of place.
It was listening to his work in the 70s - his arrangements for The Band, his productions for The Meters, Lee Dorsey and Irma Thomas, and his own solo masterpiece, the album Southern Nights - that I first realised New Orleans music had a flavour and character that couldn't be found anywhere else, not even a few miles up the river.
Determined to experience that music in its natural environment, I began making visits to the city. I first saw Toussaint perform in 1982.
His concert was on a steamboat - a kind of giant floating ballroom. He played clusters of his great songs - 'Working In A Coalmine', 'What Do You Want the Girl To Do?', 'It's Raining' - all hits he had written for other artists - as we puttered up the Mississippi.
In 1988, I was sitting in the sun at the Jazz and Heritage Festival listening to the great New Orleans blues guitarist and singer Earl King when I noticed Allen Toussaint sitting on the grass just a few feet away.
Like me, he was grooving to the music; unlike anyone else in that hot afternoon crowd, he was dressed in his customary suit and tie. Somehow, his formal appearance seemed to acknowledge the dignity of the music we were listening to.
At the end of the set, we both got up to leave and I had the opportunity to say a few words to him about how much his music meant to me.
The truth was, if it hadn't been for him I wouldn't have been in New Orleans. He thanked me for my compliments and agreed happily when I asked if I could take his photograph. He also asked whether I would like a photograph of us together.
I accosted a passing stranger, handed them my camera and posed alongside the master, but when the photos came back they had managed only to take a picture of our feet. My picture of Toussaint, however, can be seen above.
Allen may have died, but his music will live on.