As the story is generally related, Ellington was at first impressed primarily with Strayhorn's lyrics. A second meeting, this time in Newark, New Jersey, prompted Ellington to request Strayhorn's services as an arranger of some pieces for the band. In a retelling of the event, the Village Voice reported: "One detail remains consistent.... Ellington wrapped his arms around Strayhorn and announced, 'You are with me for life.'"

The next 29 years of Strayhorn's life were spent as part of the Ellington organization--writing, arranging, and sitting in on piano. A particularly notable period occurred during a strike by the American Society of Composers, Authors and Publishers (ASCAP) in 1941. As an ASCAP member, Ellington was not allowed to have his own compositions performed on the radio. Strayhorn, not a member of ASCAP, was given the opportunity to write his own pieces. The most famous of these, "Take the 'A' Train," was inspired by two subway trains that went to Harlem: the "D" and the "A." The "A" went straight to Harlem, but the "D" veered off, ending up in the Bronx. As Strayhorn was quoted as saying in Stanley Dance's book, The World of Duke Ellington: "I said I was writing directions--take the 'A' Train to Sugar Hill. The 'D' Train was really messing up everybody."

Strayhorn composed many other pieces alone, but because they were recorded by the Ellington orchestra, they were often thought of as Ellington's own works. These include "Rain Check," "Passion Flower," and "Chelsea Bridge," all from 1941, and 1949's "A Flower Is a Lovesome Thing." Each of these compositions became standards in the band's repertory.

Strayhorn's musical collaborations with Ellington from the 1950s and 1960s are numerous and include such classic compositions as A Drum Is a Woman; Such Sweet Thunder; adaptations of Russian composer Tchaikovsky's Nutcracker Suite and Norwegian composer Edvard Grieg's Peer Gynt Suite; and The Far East Suite. Jazz performers, critics, and scholars differ over whether it is possible to determine which portions of these pieces were written by Strayhorn and which by Ellington. In his book The Swing Era: The Development of Jazz, 1930-1945, Gunther Schuller points out four distinct characteristics that mark the music as Strayhorn's, and some of Ellington's players have said that they could always tell what Strayhorn had written.

Others observers feel that it is impossible to determine whose writing is whose--and believe it worthless to try. The most important thing to remember is that both composers had the same end in mind. As Strayhorn told Bill Coss in an interview for Down Beat magazine in 1962: "I'm sure the fact that [Ellington and I are] both looking for a certain character, a certain way of presenting a composition, makes us write to the whole, toward the same feeling. That's why it comes together--for that reason."
Strayhorn was small and sedate--and a homosexual at a time in America's history when it was especially difficult to be a gay man, particularly in the very heterosexual jazz world. He was adored and protected by Ellington and by the members of the band, who had several affectionate nicknames for him, among them "Strays," "Weely," and "Swee' Pea." The last, by far the most widely used, was given him by alto saxophonist Toby Hardwick, who had picked up the name from the infant in the Popeye comics.

Strayhorn's death in 1967 from cancer of the esophagus affected Ellington deeply. As Hardwick told Dance in The World of Duke Ellington, it was "the one thing I know of that really touched Duke. The one thing ... that hit him hard." Upon accepting the Medal of Freedom at the White House in 1969, Ellington recited the four freedoms by which Strayhorn lived. As recorded by Dance, they were: "Freedom from hate unconditionally; freedom from self-pity; freedom from the fear of doing something that would help someone else more than it would help me; and freedom from the kind of pride that makes me feel I am better than my brother."

In the 1970s and 1980s, Strayhorn's music became more familiar to listeners, thanks to performances and recordings of his compositions by individual artists. Tenor saxophonist Joe Henderson and trumpeter Art Farmer have each devoted albums to Strayhorn's work. After Strayhorn's death, Ellington released a tribute album to him, And His Mother Called Him Bill.