Brocchi påbörjade sin karriär i AC Milans ungdomslag och lånades i sina yngre år ut till Pro Sesto och Lumezzane. 1998 såldes Brocchi till Hellas Verona i Serie B och var med då de tog klivet upp till Serie A. Efter ett år i Serie A skrev han på kontrakt för Inter Milan2000. Under sommaren 2001 såldes han tillbaka till AC Milan i utbyte mot Andrés Guglielminpietro som gick till Inter. Han gjorde bara 15 matcher för AC Milan det året och oftast som avbytare. Han lånades i juli 2005 ut till Fiorentina med mål på en permanent övergång, men återvände till Milano i slutet av säsongen 2005/2006.