Before the song's release B.o.B. performed the song at concert on three different occasions. He debuted the song at Colorado in late August 2011, then performed the track again in Syracuse, New York on September 13, 2011 and on September 20, 2011, at Tennessee Tech University. On September 23, 2011, B.o.B released a trailer through his official website, depicting him in the studio playing the song. The song leaked two days later, this prompted a rush release of the single which was originally scheduled to premiere on October 3, 2011. The song was written by Bobby Ray Simmons, Jr., Dwayne Carter, Lukasz Gottwald and Henry Walter and was produced by Dr. Luke and Cirkut. It contains elements of dubstep and electro-hop. The official cover art for the single was released on September 26, 2011, on B.o.B's official website. The cover depicts an open grassy landscape on the bottom portion of the cover and a large open sky with a central mystical entity that resembles a nebula centered in the sky above. Soon after the release of "Strange Clouds" it quickly took the top spot in digital sales on iTunes. B.o.B included the song on his eighth mixtape, E.P.I.C (Every Play Is Crucial).
The official remix to "Strange Clouds" was released 12 January 2012 and features fellow Atlanta rappers T.I. and Young Jeezy. The remix maintains the original production from Dr. Luke, however B.o.B performs a new verse and a slightly modified chorus.
The second official remix will feature rappers Tech N9ne and Kid Cudi. It was mentioned on February 6, 2012 by Tech N9ne through his official blog & a tweet he responded to a fan on his Twitter account. It was later confirmed on April 5, 2012 by B.o.B through a tweet he responded to a fan on his Twitter account. The song was almost performed live during a January, 2012 concert in Australia where Tech N9ne and Kid Cudi were both performing, but the performance never happened due to a stalker threatening Tech N9ne during the show. Although the remix has been recorded, it has not yet been released. It is not clear as to if the remix will ever see the light of day.
On the week of October 10, 2011 the song debuted at number seven on the U.S. Billboard Hot 100 making it the "Hot Shot Debut" of the week. In the first week of the song's release it sold 197,000 digital copies debuting at number three on the U.S. Hot Digital Songs. "Strange Clouds" marks his best debut sales week for a single, previously held by the 137,000 launch of "Airplanes" on May 1, 2010. As of February 9, 2012, "Strange Clouds" has been certified platinum by the RIAA.