Columbia Records had recently acquired Van McCoy in 1965. David Kapralik made McCoy known to Columbia vice-president, William P. Gallagher. Kapralik was also McCoy's manager. In spite of Van McCoy's history as a composer, Columbia wanted to push him as a recording artist. Billboard wrote in an October 2 article that the Columbia was using its might in a promotion to pitch McCoy via a coast-to-coast tour of radio stations, extensive trade advertising, and promotional mailing to disk jockeys etc. Amongst this, there was to be a cover story about McCoy on the record company's nationally distributed company magazine, Insight.
This was McCoy's first single for Columbia. It consisted of two of his originals, "Butterfly" and "Keep Loving Me".
[1] Billboard had "Keep Loving Me" as the A side and "Butterfly" as the B side. The arrangements were handled by Gary Sherman. The single was released on Columbia 43415.[2] There was a special white label promotion of the single that came with a picture cover. It read Columbia Records INTRODUCES VAN MCCOY BUTTERFLY b/w KEEP LOVING ME.[3] The October 2 issue of Billboard had it in the Pop Spotlights Top 60 section, a record predicted to reach the top 60 of the HOT 100 Chart.[4] The following week, Billboard ran a picture of McCoy seated, signing his contract with Columbia vice-president William P. Gallgaher and manager Dave Kapralik looking on.[5] A full-page advert for the single with McCoy pictured appeared on page 5 of the same issue.[6]
On the week of October 25, in her New York column, Harriet Wasser (R. P. M.'s New York correspondent[7]) said that McCoy singing on "Butterfly" sounded a bit like Nat King Cole and Johnny Mathis.[8]