Andreas Heinze wurde in Leisnig geboren und erhielt seine erste musikalische Ausbildung als Mitglied des Dresdner Kreuzchores. Anschließend studierte er an der Hochschule für Musik Carl Maria von Weber in Dresden Gesang und Gesangspädagogik bei Helga Köhler-Wellner sowie Chordirigieren bei Hans-Dieter Pflüger, dem damaligen Chordirektor der Semperoper. Nach Solo-Examen, Diplom und Praktikum begann der Bass 1988 sein Engagement im Chor der Sächsischen Staatsoper Dresden. Mit ihm gastierte er u.a. mehrfach bei den Salzburger Festspielen sowie in Japan und beim Opernfestival in Savonlinna. Zudem übernahm er chorsolistische Partien z.B. in Les Contes d’Hoffmann, La bohème, Idomeneo, La traviata, Capriccio und Der Rosenkavalier. Gleichzeitig unterrichtete er von 1989 bis 1999 im Opernchorstudio. Zusätzlich leitete er von 1994 bis 2014 den Kinderchor der Sächsischen Staatsoper, der für seine künstlerischen Leistungen im Jahr 2013 mit dem Preis der Stiftung zur Förderung der Semperoper ausgezeichnet wurde. Neben seinen Aufgaben in der Oper tritt Andreas Heinze regelmäßig auch solistisch auf. Dabei umfasst seine Konzerttätigkeit sowohl kirchenmusikalische Soloprogramme als auch die Basspartien der großen Oratorien verschiedenster Komponisten.