On November 9, 1989, Rawlco Communications, owner of CFGO, was granted a license for a new FM station. Rawlco proposed to use the frequency 92.1 mHz, but conflicted with CBO-FM, located on 91.5. On April 5, 1991, Rawlco's application to use the 100.3 frequency was granted. The station's radiated power would be 80,000 watts. On August 12, 1991, at 6:25 PM, the station signed on, with the official launch the following morning at 6 AM. The first song on "Majic 100" was "Do You Believe in Magic" by The Lovin' Spoonful. On March 11, 1992, the station increased its power to 100,000 watts, with a transmitter on the Ryan Tower in Camp Fortune.
The station was mostly known for being the #1 FM station in Ottawa for most of the 2000s, like its Brockville and Vancouver outlets with the same AC format that leads the ratings in those areas. This status was dropped in the late 2000s, whereas Majic has now officially been beaten by Newcap Radio's contemporary hit radio outlet CIHT-FM. However, the station usually is ranked in the Top 5 Anglophone ratings for the Ottawa/Gatineau market according to BBM.
As of 2010, due to increased competition from adult contemporary station CJWL-FM (which leans heavy towards softer content), the station removed its longtime oldies show aired on Sunday mornings and added more upbeat Hot AC songs to the playlist; however, they are still an adult contemporary station due to Rogers Media's CISS-FM serving as the hot AC station for Ottawa. In fact, 1960s songs have been largely dropped from the station, while still playing 1970s songs such as More Than a Feeling by Boston. Most of the 1970s songs have been dropped as of mid-2013. Mediabase and Nielsen BDS still report the station on the Canadian AC panel.
Like many other AC stations, CJMJ airs wall-to-wall Christmas music during the months of November and December.