She took a clerical job for some years and supplemented her income by taking work as an extra in Hollywood, appearing with Lana Turner in The Prodigal (1955) and in The Ten Commandments (1956). Liston returned to Gillespie for tours sponsored by the U.S. State Department in 1956 and 1957, recorded with Art Blakey's Jazz Messengers (1957), and formed an all-women quintet in 1958. In 1959, she visited Europe with the show Free and Easy, for which Quincy Jones was the music director. She accompanied Billy Eckstine with the Quincy Jones Orchestra on At Basin Street East, released on October 1, 1961, by Verve. In the late 1950s, she began collaborating with pianist Randy Weston, arranging compositions (primarily his own) for mid-size to large ensembles. This association, especially strong in the 1960s, would be rekindled in the late 1980s and 1990s until her death. In addition, she worked with Milt Jackson, Clark Terry, and Johnny Griffin, as well as working as an arranger for Motown, appearing on albums by Ray Charles. In 1964, she helped establish the Pittsburgh Jazz Orchestra. In 1971 she was chosen as musical arranger for Stax recording artist Calvin Scott, whose album was being produced by Stevie Wonder's first producer, Clarence Paul. On this album she worked with Joe Sample and Wilton Felder of the Jazz Crusaders, blues guitarist Arthur Adams, and jazz drummer Paul Humphrey. She worked with youth orchestras in Watts, California before accepting an invitation from the Government of Jamaica in 1973 to become the Director of Afro-American Pop and Jazz at the Jamaica School of Music. She returned to the U.S. in 1979 where she was honored at the first Women's Jazz Festival in Kansas City, Missouri, and the Salute to Women in Jazz in New York, later forming a new band, Melba Liston and Company. During her time in Jamaica, she composed and arranged music for the 1975 comedy film Smile Orange, starring Carl Bradshaw, who three years earlier starred in the first Jamaican film, The Harder They Come (1972). She also served as composer, arranger, and musical director of The Dread Mikado, a theater production considered emblematic of the Jamaican cultural revolution. She was forced to give up playing in 1985 after a stroke left her partially paralyzed, but she continued to arrange music with Randy Weston. In 1987, she was awarded a Jazz Masters Fellowship from the National Endowment