Verein

Leitner begann seine Karriere beim SV Breitenau in der Steiermark. 2007 wechselte er zum SK Sturm Graz, den er eine Saison darauf für die Jugendabteilung des SC Wiener Neustadt verließ. 2009 spielte er bei der FK Austria Wien-Jugend, ehe er 2009 zur Jugendabteilung des FC Admira Wacker Mödling stieß.

2011 wurde er in den Kader der zweiten Mannschaft, welche in der Regionalliga Ost aktiv ist, geholt. Sein Debüt gab er am 18. März 2011 gegen den SC Neusiedl am See, als der Torhüter durchspielte. In seiner ersten vollen Saison kam Leitner auf 15 Einsätze. Danach wurde er zweiter Torwart der ersten Mannschaft und kam unter Trainer Dietmar Kühbauer am 1. Dezember 2012 zu seinem Bundesligadebüt. Im Spiel gegen den SV Mattersburg wurde er in der 45. Minute, nach einer roten Karte für den Stammtorhüter Patrick Tischler, für Lukas Thürauer eingewechselt. Das Spiel im Mattersburger Pappelstadion wurde 0:3 verloren.

Nach einer öffentlichen Diskussion über die Vertragsverlängerung bei der Admira wurde Andreas Leitner suspendiert und sein Vertrag nicht mehr verlängert. Daraufhin wechselte der Torhüter im Juni 2015 zum Zweitligisten SK Austria Klagenfurt. Überraschenderweise wurde am 23. Juli 2015 bekannt, dass Leitner doch einen langfristigen Vertrag beim FC Admira Wacker Mödling unterzeichnet hat und die Saison 2015/16 nur leihweise am Wörthersee verbrachte.

Nationalmannschaft

International spielte Leitner bisher für die österreichische U-16, U-17, U-18 und U-19-Nationalmannschaft.