En 1977 formó con Vince Clarke un dúo llamado No Romance in China, después Clarke tuvo otra banda llamada The Plan y compartían shows con Martin Gore y su grupo French Look, finalmente, en 1980, Clarke, Gore y Fletcher unieron fuerzas para formar el trío Composition of Sound que, al poco tiempo, con el ingreso del cantante David Gahan, cambió su nombre a Depeche Mode.

Vince Clarke abandonó el grupo después de su primer disco, tras unos meses fue sustituido por Alan Wilder quien resultó ser enormemente talentoso.

Curiosamente, Fletcher fue el primer miembro del grupo que realizó un proyecto solista, en 1984 durante las grabaciones de Some Great Reward cuando grabó su álbum Toast Hawaii en el cual Martin Gore y Alan Wilder colaboraron tocando el piano.

En 1990 se ausentó poco antes de que concluyeran su disco de ese año, Violator, y en 1994, cuando la gira Devotional Tour se extendió por Canadá y Estados Unidos como Exotic Tour, debido a una crisis nerviosa abandonó la banda, por lo cual Daryl Bamonte tomó su lugar para concluir la gira.

En 1995 Alan Wilder abandonó el grupo y este entró en la peor crisis que habían tenido hasta ese momento; mucho se habló de su posible disolución.

En febrero de 2010, en un concierto especial de DM en Londres, apareció sin previo aviso Alan Wilder para tocar con Martin Gore el tema Somebody, al salir, Fletcher lo topó en el escenario y lo abrazó, conciliando aquella vieja rencilla nunca publicitada.