Grupa została założona w Poznaniu w 2004 roku przez Michała Wiraszkę, Piotra Maciejewskiego i Szymona Waliszewskiego. Jej członkowie przyznają się do inspiracji takimi wykonawcami, jak: The Smiths, The Velvet Underground, Modest Mouse, Guided by Voices czy Republika. W 2005 roku na składance Tribute to Partia ukazał się cover utworu "Nieprzytomna z bólu". Był to pierwszy zarejestrowany w studiu materiał grupy. Zespół został obwołany odkryciem roku 2006 przez miesięcznik Machina i Program 3 Polskiego Radia. Pierwszy singel zespołu pt. Miasto doznań osiągnął w maju 2007 r. 7. miejsce na Liście Przebojów Programu Trzeciego Polskiego Radia.
19 listopada ukazał się debiutancki album grupy, noszący tytuł Terroromans, uznany za "Płytę Roku" przez słuchaczy PR3. Zespół zdobył także tytuł "Zespołu Roku 2007" Programu 3 Polskiego Radia. Ponadto grupę uhonorowano trzema nagrodami "Miazga 2007" magazynu Pulp, w kategoriach zespół, płyta i piosenka (Miasto doznań) roku. Głos Wielkopolski przyznał zespołowi "Medal Młodej Sztuki 2007". Muchy zostały również nominowane do Eska Music Awards 2008 w kategorii "Album roku ROCK" i do Fryderyka 2008 w kategorii "Nowa twarz fonografii" a także do nagrody Nocne Marki 2008 pisma Aktivist w kategorii "zespół roku". W styczniu 2008 roku do zespołu dołączył Tomasz Skórka, który wystąpił po raz pierwszy podczas transmitowanego na antenie Programu 3 Polskiego Radia koncertu w studiu im. Agnieszki Osieckiej. W ciągu dwóch lat od debiutu zespół zdążył zagrać trzy trasy koncertowe oraz zawitać na wszystkich najważniejszych festiwalach (duża scena na Opener Festival, Festiwal w Jarocinie, Seven Festival Music & More w Węgorzewie, Cracow Screen Festival oraz Off Festival).
W październiku 2009 roku zespół rozpoczął pracę z poducentem Marcinem Borsem nad nowym albumem. 8 marca 2010, nakładem Sony Music Poland, miała miejsce premiera drugiego albumu zespołu Muchy - Notoryczni debiutanci. Pierwszy promujący płytę singiel - Przesilenie - wspiął się na 1. miejsce list przebojów Programu Trzeceigo Polskiego Radia, Radia Merkury i Radia Afera. W 2010 roku zespół zagrał ponad 70 koncertów. Muchy jako jedyny polski zespół wystąpił po raz drugi na głównej scenie Opener Festival. Ponadto latem 2010 roku grupa zagrała jeszcze na głównych scenach: Coke Live Music Festival, Festiwal w Jarocinie, Off Festival oraz Seven Festival w Węgorzewie. W sierpniu 2010 roku do sklepów trafiła reedycja debiutanckiego albumu Terroromans.
W lutym 2011 roku jeden z założycieli zespołu Piotr Maciejewski opuścił skład zespołu. Powodem była chęć zajęcia się solowymi projektami[1]. Jego miejsce zajął Damian Pielka, który wcześniej występował m.in. z Lechem Janerką. We wrześniu 2012 roku wydany został trzeci album studyjny zespołu zatytułowany Chcecicospowiedziec. Materiał na płytę był nagrywany we Wrocławiu i Srebnej Górze, a produkcją ponownie zajął się Marcin Bors. Pierwszy utwór z wydawnictwa, Nie przeszkadzaj mi, bo tańczę, został opublikowany jeszcze w 2011 roku.