Stationery Stores Football Club was founded in 1958 by Israel Adebajo, who ran the very successful Nigerian Office Stationery Supply Stores Limited. They immediately established themselves as one of the dominant teams in Lagos and Nigeria, supplying the bulk of the first team players of the national team and winning a total 13 Lagos State Challenge Cups, the preliminary round for the Nigerian FA Cup, and 4 National FA Cup competitions. The club's glory years started in 1967. Their fluid and entertaining style of play endeared the club to Lagos fans as they delivered two FA Cups within that period. The first 11 of the Nigerian national team in the 1968 Mexico City Olympic football event had 9 Stationery Stores players, including Sam Opone and Peter Fregene. The team also provided a steady supply of goalkeepers to the Nigerian national team—The Super Eagles, notable ones being the celebrated Peter Rufai (who captained Nigeria to her first World Cup in 1994) and Ike Shorounmu. Between 1973 and 1993, Stores was in the top division of Nigerian football. Throughout those years, the team enjoyed a healthy but sometimes acrimonious rivalry with two equally big clubsides—WNDC (later IICC) Shooting Stars (now known as 3S Football Club) and the redoutable Enugu Rangers International F.C.
Stationery Stores would win the Nigerian league in 1992, only to be relegated the following year for failing to complete its fixtures, not because the Club finished in the relegation spot. The team continued the next five seasons in the second division. However, in March 1998, the NFA was compelled to cancel all outstanding Pro League Second Division games involving Stationery Stores following an injunctive order issued by a Lagos High Court restraining Stationery Stores from playing any Pro League games pending the resolution of a lawsuit filed before the court to determine the ownership and control of the club. This action constituted the culmination of a long-festering ownership dispute involving two of the Adebajo siblings (each of whom was a director of The Nigeria Office Stationery Supply Stores Limited). The ownership tussle was thus laid to rest by the subsequent ruling of the court. However, while it lasted, that court process had a negative effect on the much-celebrated clubside. Its net effect was that throughout the course of the 1998 football season, its players were compelled to campaign without the benefit of formal contracts, sign-on fees, bonuses or club-supplied playing equipment. The team however continued to compete for honours up until the 1998 season but could not continue thereafter.
The Club returned to the professional level in the summer of 2004 but was relegated at the end of that season. Tired of the long-running underachieving status of the Club, its Supporters Club, generally organised in Chapters and autonomous sub-units, came together in 2007 to start a vigorous and well-coordinated campaign for the return of the Club. They engaged in various rounds of consultations with many stakeholders, including with the owners of the Club and deployed a sustained media strategy which contributed to strengthening efforts of the Directors of the Club to revive and rejuvenate its fortunes. Stationery Stores FC thus returned to the Nigerian Professional League in the 2014 soccer season, buying up the slot of Union Bank FC. The Supporters also re-structured, setting up the first Football Supporters Trust in Nigeria, with a view to giving its members better representation in the Club and supporting the Club materially as well.
The Club made a much-heralded return to the Nigerian Professional League in the 2014/2015 soccer season, whose star match was the twin fixture with one of its arch rivals and powerhouse of Nigerian soccer—3SC Football Club (aka as Shooting Stars). In a tension-soaked encounter in Lagos, Stores beat Shooting by two unreplied goals. The team also campaigned in the internationally famous Copa Lagos Beach Soccer Tournament, where its match with the famed Barcelona FC was not only a sell-out and the star match, but was televised across the African continent to the delight of the fans of Stationery Stores FC beyond the shores of Nigeria.
Faced by a completely different soccer environment than it was used to in its hey days, Super Stores FC would soon elect not to play any competitive match the following season in order to re-organise and restructure to enable it fit into the changes that have taken place in the said Nigerian football environment. This done, it returned to competitive soccer in the 2017/2018 soccer season, competing in the Federation (FA) Cup and impressing its numerous fans and soccer administrators as it won a string of games. Though it ended up not winning the Cup, it famously did not lose in open play. Consistent with its business plan, it engaged in a series of local and international friendlies, including winning the Commemorative Tournament to celebrate the founding and 50th anniversary of Lagos State in June 2017.