Oorspronkelijk geformeerd in de late jaren 1990 door Brendan Canning[2] en Bernard Maiezza[3] na de ontbinding van hun vorige bands hHead en Change of Heart, bracht de band in 2001 een titelloos album uit met de bezetting Evan Cranley, Danko Jones, Spookey Ruben en Ian Blurton[4], maar ging vervolgens op pauze toen Cannings andere project Broken Social Scene, doorbrak tot een massale populariteit. Na de aankondiging van Broken Social Scene in 2011 dat ze op pauze gingen, bliezen Canning en Maiezza Cookie Duster nieuw leven in, werkend met een nieuwe bandopstelling waaronder zanger Jeen O'Brien[5], gitarist Matt Murphy en drummer Damon Richardson[6] (Danko Jones). Canning, Bernard, Maiezza, O'Brien, Murphy en Richardson brachten in juni 2012 het album When Flying Was Easy uit. De nieuwe bezetting begon begin 2013 live op te treden en maakte hun debuut op het Wavelength Music Festival in Toronto.