The record producer Alfred Lion, who founded the Blue Note label, had three great enthusiasms among jazz pianists: Thelonious Monk, Herbie Nichols and Andrew Hill.

Monk swiftly found fame and success, Nichols died young before achieving his true potential and Hill gradually progressed from being something of an acquired taste into one of the recognised masters of contemporary jazz. Hill was fond of exotic hats and shaded spectacles, and he suffered from a bad stammer: this much is certain. Few figures in the American mainstream have had quite so many myths and stories woven around them, and Hill’s gnomic refusal to confirm or deny these at various stages in his life encouraged a somewhat kaleidoscopic view of his career. He was, it was ru-moured, born in Haiti, he had lessons as a child from Paul Hindemith, he had held teaching fellowships at leading universities including Colgate. But such colourful fantasies were largely just that, adding an air of mystery to his life and work.

His main period of activity was for Blue Note in the 1960s. His albums from that time, such as Black Fire and Point of Departure, experimenting with unusual forms, uneven numbers of bars, shifts in metre and unorthodox instrumentation, stand as a remarkable corpus of exploratory thinking, alongside the more widely known innovations of John Coltrane (with whom Hill recorded occasionally) and Miles Davis.

He moved forward into free jazz, touring the UK in the 1990s with a free-form trio, and he returned in later life to more formal structures, notably in an Anglo-American big band that toured the UK in 2003.

Yet in this apparent return to earlier forms, Hill had a surprise up his sleeve: “I’ve written music where the sections of each piece change from one performance to the next,” he told The Times, “so that it’s not in the least predictable how each performance will develop.”

This commitment to spontaneity and improvisation won him many admirers among such young British players as his colleagues Jason Yarde, Byron Wallen and Denys Baptiste.

Andrew Hill was born and grew up in Chicago. As a boy, he got to know the pianist Earl Hines, who lived on his newspaper delivery round, and who encouraged Hill after hearing him busking on the accordion outside the Hurricane Lounge.

It is claimed he studied with Hindemith as a teenager, but what is known is that in his teens he played R&B with Paul Williams and backed up the likes of Charlie Parker and Johnny Griffin at local clubs. After spells as accompanist to Dinah Washington and then with Roland Kirk’s band, he ended up in New York as a free-lance, beginning his Blue Note career in 1963.

He formed close associations with several of the Blue Note roster, in particular the vibra-phone player Bobby Hutcher-son, with whom he continued to perform sporadically until the late 1990s.

Lion realised that Hill’s work was not to everyone’s taste but he recorded him often, and in the 1990s, when 1960s jazz first began to appear on CD, a considerable amount of new material by Hill was issued. But by then his career had moved on. He recorded as a soloist in the early 1970s for several labels, and toured and performed under the auspices of the Smithsonian Institution early that decade, before moving to relative seclusion in California, to care for his terminally ill wife.

His return to the public eye, after her death in 1989, coincided with the relaunch of Blue Note under its current president, Bruce Lundvall. His new albums Eternal Spirit and But Not Farewell revealed his talent to be as acute as ever, and his thirst to explore new forms and timbres unquenched.

He worked often with the young saxophonist Greg Osby, and gathered around him a series of innovative ensembles, from trios to quintets and sextets. His album Dusk (2001), made for the Palmetto label, was something of a landmark, indicating new territory to explore with a small group in which his collaborations with the trumpeter Ron Horton and saxophonist Marty Ehrlich were exemplary. That album contained a tribute to the late saxophonist Thomas Chapin. Hill and Chapin received treatment for cancer at the same hospital at the same time.

Although Hill recovered to continue his career with great success for several years, he believed he was on borrowed time, and in a remarkable late burst of creative energy stretched the boundaries of his art to attempt something new in every concert.

He was rewarded with the Danish Jazzpar prize in 2003, an award regarded in the jazz world as equivalent to a Nobel prize.

Hill was critical of such contemporaries as Archie Shepp (with whom he shared a double bill at the Queen Elizabeth Hall, London) for relying on past triumphs. “I always want to come up with something different,” he told The Times, and as if to prove his point he made Time Lines (2006). It is widely regarded as one of his finest records, combining his gift for melody with daring experiment. When this was recorded he already knew he had terminal lung cancer, but he continued to perform, appearing in a trio concert at a Manhattan church only three weeks before his death.

Hill is survived by his second wife, Joanne.

Andrew Hill, jazz pianist, was born on June 30, 1931. He died on April 20, 2007, aged 75