The Ikon began with a painting. In 1964, the Birmingham art collector Angus Skene bought David Prentice's canvas Kate and the Waterlilies. The two fell into conversation about how little support Birmingham's institutions offered to living artists. Prentice brought in three colleagues from the Birmingham School of Art: Sylvani Merilion, Jesse Bruton, and Robert Groves. Together they cooked up the idea of a gallery dedicated entirely to new work. Groves, who was interested in the icons of the Eastern Orthodox Church, suggested the name. The others liked it because it divided beautifully geometrically and was splendid in all directions. Skene paid for the kiosk in the Bull Ring. The artists ran the place themselves, sometimes with their spouses helping at weekends. The first exhibition showed work by John Salt, a Birmingham painter who would soon emerge as a pioneer of British photorealism.

The kiosk lease expired after three years. With Arts Council support, the Ikon moved in 1968 to a former mortuary in the basement of Queens College in Swallow Street. Over the next four years they staged 93 exhibitions and 40 group shows, an extraordinary pace for a tiny organisation. When that lease ended, Simon Chapman, who had previously run the Birmingham Arts Lab, took over and led the gallery in a more ambitious direction. In autumn 1972 the Ikon relocated to the Birmingham Shopping Centre, a brand-new mall on top of the rebuilt New Street Station. The new space was four times bigger than Swallow Street and forty times bigger than the Bull Ring kiosk. The opening show, large chalk drawings by John Walker, drew hundreds and sometimes more than a thousand visitors a day, many of them seeing modern art by living artists for the first time. The Ikon was suddenly one of the most important contemporary galleries outside London.

By 1978 the Ikon had outgrown the shopping centre and moved to a former carpet shop in John Bright Street next to the Alexandra Theatre. It stayed there for nearly two decades. The breakthrough came in 1997, when the gallery moved into its present home, the former Oozells Street Board School, designed by John Henry Chamberlain in 1877. The Grade II listed neo-Gothic building had lost its central tower during 1960s alterations, and the conversion by architects Levitt Bernstein restored it. National Lottery funding covered much of the cost. Cafe Ikon opened on the ground floor in December 1998, designed by Birmingham architects The Space Studio. The new building sits on a corner of Brindleyplace, the canal-side regeneration that had transformed the area around Gas Street Basin in the early 1990s, putting the gallery at the heart of the city's reinvention as a cultural destination.

In 2011 the Ikon started a long collaboration with Turner Prize-winning artist Gillian Wearing on a public sculpture called A Real Birmingham Family. Wearing put out an open call for nominations, asking what a typical Birmingham family looked like, and selected sisters Roma and Emma Jones, both single mothers, with their sons Kyan and Shaye. The bronze cast was unveiled in Centenary Square outside the Library of Birmingham on 30 October 2014. The sculpture is taller than life, the four figures standing together with quiet dignity. It is the antithesis of the heroic 19th-century bronzes scattered across the city, and it has become one of the most photographed pieces of public art in the Midlands. The gallery's solo programme since 2000 has included international names like Olafur Eliasson, Cornelia Parker, and On Kawara, but A Real Birmingham Family remains the work that most fully expresses the Ikon's founding promise of putting art into the city rather than holding it apart.