When Nancy met Julian "Cannonball" Adderley, he suggested that she should move to New York City, believing that the big city would be the venue in which her career could bloom. In 1959, she relocated to New York with a goal of obtaining Cannonball’s manager John Levy as her manager and Capitol Records as her label. Within four weeks of her arrival in New York she got her first big break, a call to fill in for Irene Reid at "The Blue Morocco". The club booked Wilson on a permanent basis; she was singing four nights a week and working as a secretary for the New York Institute of Technologyduring the day. John Levy sent demos "Guess Who I Saw Today", "Sometimes I’m Happy", and two other songs to Capitol. Capitol Records signed her in 1960.
Nancy’s debut single, "Guess Who I Saw Today", was so successful that between April 1960 and July 1962 Capitol Records released five Nancy Wilson albums. Her first album, Like in Love, displayed her talent in Rhythm and Blues, with the hit R&B song "Save Your Love for Me." Adderley suggested that she should steer away from her original pop style and gear her music toward jazz and ballads. In 1962, they collaborated, producing the album Nancy Wilson and Cannonball Adderley, which propelled her to national prominence, and Wilson would later appear on Adderley's live albumIn Person (1968). Between March 1964 and June 1965, four of Wilson's albums hit the Top 10 on Billboard's Top LPs chart. In 1963 "Tell Me The Truth" became her first truly major hit, leading up to her performance at the Coconut Grove in 1964 – the turning point of her career, garnering critical acclaim from coast to coast. TIME said of her, "She is, all at once, both cool and sweet, both singer and storyteller." In 1964 Nancy released what became her most successful hit on the Billboard Hot 100 with "(You Don't Know) How Glad I Am", which peaked at No. 11. From 1963 to 1971 Wilson logged eleven songs on the Hot 100, including two Christmas singles. However, "Face It Girl, It's Over" was the only remaining non-Christmas song to crack the Top 40 for Wilson (#29, in 1968).