During this time, Frank Sinatra formed Reprise Records and hired Costa to arrange the album "Sinatra and Strings", released in 1962. This set of standard ballads would remain one of the most critically acclaimed works of Sinatra's Reprise period. His later work moved away from orchestra arrangement. Songs on the album include "All or Nothing at All", a verse-only version of "Stardust", a ballad rendition of "Night and Day" which provided a contrast to Sinatra's more familiar big band version, and "Come Rain or Come Shine", which frequently is included in compilations from Sinatra's Reprise years. During the next year, Costa was asked to arrange for the Sarah Vaughan album, "Snowbound". Barbra Streisand used the same arrangement of "Snowbound" for her second Christmas album for Sony in 2001. Costa also arranged Tony Bennett's 1965 album "".