Die Band ist ein Projekt des kanadischen Produzenten Nasri Atweh, der für seine Arbeit unter anderem mit Justin Bieber, Pitbull, aber auch den No Angels bekannt geworden ist. Zusammen mit dem Songwriter Mark Pellizzer schrieb er 2012 den Song Rude. Dann stellte er mit ihm selbst als Sänger, mit Pellizzer als Gitarrist, Ben Spivak als Bassist und Alex Tanas als Schlagzeuger die Band Magic! zusammen. Als Vorband von Matisyahu gingen sie 2013 auf Tour und fanden mit Sony Music im selben Jahr ein Label, das Rude als ihre Debütsingle veröffentlichte. Außerdem produzierten sie für das folgende Jahr ihr erstes Album Don’t Kill the Magic. Bereits Ende 2013 erschien die Single in Australien und Neuseeland und konnte sich dort jeweils auf Position zwei in den Charts platzieren. Ende April 2014 wurde sie in den USA veröffentlicht und arbeitete sich in den US-Singlecharts immer weiter nach oben, bis sie im Juli schließlich Platz eins erreichte. Das Album stieg im Juli auf Platz sechs ein. Danach wurde das Lied auch in Europa veröffentlicht und kam unter anderem auf Platz eins in Großbritannien.
Zum offiziellen FIFA-Album One Love, One Rhythm zur Fußball-Weltmeisterschaft 2014 trugen Magic! den Song This Is Our Time (Agora É A Nossa Hora) bei.