Neal Paul Hefti was born on October 29, 1922, in Hastings, Nebraska, to a family that depended on charity when he was small. He started on trumpet in school at eleven and grew up in and around Omaha, where the Southwest territory bands and touring New York players passed through; he later named Harry Edison and Buck Clayton of Count Basie's band, and Dizzy Gillespie with Cab Calloway, as the trumpeters who struck him most. By high school he spent his summers in territory bands to help his family, and in 1939, still a junior at Omaha's North High School, he began writing arrangements of vocal ballads for local bands, among them Nat Towles's, whose book included his chart of "Anchors Aweigh." Some of the material he wrote in high school was also used by the Earl Hines band.

In 1941 he left for New Jersey with Dick Barry's band, was fired after two gigs because his sight-reading was not good enough, and ended up in Bob Astor's band, where the drummer Shelly Manne roomed with him and remembered him writing a full chart for the next night with no score. Classified 4-F during the war after a car in New York broke his pelvis, he played with Bobby Byrne in late 1942 and then with Charlie Barnet, for whom he wrote the arrangement of "Skyliner." He spent his evenings on 52nd Street, slipping into club kitchens to hear Gillespie and the young bebop players. After a stretch with Les Lieber's rhumba band in Cuba he joined Charlie Spivak in 1943, which took him to California for a band film, and he stayed there, playing a few months with Horace Heidt in 1944.

That year he joined Woody Herman's First Herd as a trumpeter, in what he later called his first real jazz band, one whose players carried Duke Ellington and Herman records on the road. The band was among the first big bands to work with bebop ideas, and Hefti, who had absorbed the music on 52nd Street, wrote much of that material; the bassist Chubby Jackson credited him with putting bop figures into the ensemble passages. He composed "Wild Root" and "The Good Earth," arranged "Blowin' Up a Storm," and with the pianist Ralph Burns arranged "Caldonia," a Louis Jordan hit that the band recorded on February 26, 1945. The eight-bar trumpet passage near the end of that record, often attributed to Gillespie, was Hefti's writing, and it is said to have been what drew Igor Stravinsky to the band, for which Stravinsky later wrote the Ebony Concerto. On November 2, 1945, Hefti married the band's vocalist, Frances Wayne. They both left Herman in late 1946 so that he could write full time.

As a freelancer he wrote for Buddy Rich's band, Billy Butterfield's, and George Auld's (including "Mo-Mo"), for Harry James's band in the late 1940s, and for Charlie Ventura's short-lived big band, in which he also played and arranged "How High the Moon." He formed his own band in 1947 with Wayne as the featured singer and led it off and on through the 1950s. In December 1947 he recorded "Repetition," a Cuban-flavored piece for big band and strings that he had written with no soloist in mind; Charlie Parker, who was in the studio, asked to play on it, and the result appeared on Norman Granz's anthology The Jazz Scene (1949).

In 1950 he began writing for Count Basie, whose band came to be called the "New Testament" ensemble. Basie recalled Hefti coming by to offer to put something in the book, returning with "Little Pony," then "Sure Thing," "Why Not?" and "Fawncy Meeting You," and the band taking to his writing from then on. The tight, carefully fitted charts gave the orchestra an ensemble identity that lasted more than twenty years. The Atomic Mr. Basie (Roulette), recorded October 21 and 22, 1957, was built from his compositions and arrangements, among them "Li'l Darlin'," "Splanky," "The Kid from Red Bank," "Flight of the Foo Birds," "Fantail" and "Teddy the Toad." It was Basie's first Roulette album and won two Grammy Awards at the first ceremony in 1959, for Best Jazz Performance, Group and Best Performance by a Dance Band. Basie, Hefti and the producer Teddy Reig made Basie Plays Hefti about six months later, with "Cute" among its eleven Hefti pieces. His arrangements also shaped Basie's sound on standards: Frank Sinatra's Sinatra-Basie (Reprise, 1962), recorded in Hollywood in October 1962, used Hefti charts written for the band's instrumentation, and Sinatra and Swingin' Brass (Reprise, 1962) was the first full Sinatra album with Hefti as arranger and conductor.

Through the 1950s Hefti recorded under his own name for Coral, Epic, RCA Victor and Vik, and he earned a Grammy nomination for his album Jazz Pops (Reprise, 1962). Miles Davis said in a 1955 interview that Basie's band would not sound as good without Hefti but that Hefti's own band could not play those arrangements nearly as well, a remark that fits the way his reputation rested on his writing more than his bandleading. He wrote the string arrangements for Clifford Brown's Clifford Brown with Strings (EmArcy), recorded January 18 to 20, 1955, and adapted and arranged twelve songs for Della Reese's Della (1960), another Grammy nominee. Later in the decade he gave up playing the trumpet altogether to concentrate on writing and conducting, working behind singers in the studio and on television programs including Arthur Godfrey's and Kate Smith's.

Hefti moved back to Los Angeles in 1960, and over the next decade much of his output went to film and television. His scores included Sex and the Single Girl (1964), How to Murder Your Wife, Boeing Boeing, Harlow and Synanon (all 1965), Lord Love a Duck and Duel at Diablo (1966), Barefoot in the Park (1967) and The Odd Couple (1968); "Girl Talk," from Harlow, drew two Grammy nominations. In 1961 he also became the chief artists and repertoire representative at Reprise Records. His theme for the Batman television series (1966), a twelve-bar blues riff on three chords, won the Grammy for Best Instrumental Theme and was a hit single for the Marketts and for Hefti himself. His Odd Couple film theme returned in the television series of the early 1970s, and his work on that show earned two more Grammy nominations. After Frances Wayne passed away in Boston on February 6, 1978, he gradually withdrew from music and in later years said he was mostly looking after his copyrights. He was named to the ASCAP Jazz Wall of Fame in 2005, and he passed away of natural causes at his home in Toluca Lake, California, on October 11, 2008, at 85.

Hefti's strength was writing cut to fit the players who would perform it. For Basie he wrote short, tightly scored pieces that matched the band's soloists and kept the result sounding like Basie, a point Barry Ulanov made in his notes for Atomic Basie; as with Duke Ellington's writing for his own orchestra, the same charts sounded less convincing when another band, including Hefti's own, played them. In the First Herd he carried the vocabulary he had picked up from Dizzy Gillespie on 52nd Street into big-band ensemble writing, and as a trumpeter he played in a bop-inflected style. Alongside Ernie Wilkins and Frank Foster, he helped build the 1950s book of the Count Basie Orchestra, and Frank Wess had a showcase in his flute-and-brushes "Cute." The proportions of the career are worth stating plainly: his standing in jazz rests on the Herman and Basie years, but from 1960 the larger share of his output was film and television scoring, and for most listeners his name is attached to Batman and The Odd Couple. The Batman theme is built on a simple, repeating, blues-based figure, and its eleven shouts of the title are sung by an eight-voice chorus rather than played by horns, as Hefti himself said. In his screen scores he could still work in echoes of his jazz background, though they were written to the demands of the picture.