Kleinheisler begon met voetballen bij Kerületi om vervolgens bij Felcsút en later bij Videoton in de jeugd te gaan spelen. Kleinheisler begon zijn professionele carrière bij Puskás in het seizoen 2012/13. Hij speelde één seizoen voor deze ploeg en maakte acht treffers in 27 duels. Vervolgens maakte hij een overstap naar Videoton, waar Kleinheisler in de periode van 2013 tot en met 2016 in totaal 30 wedstrijden speelde, waarin hij viermaal scoorde. Tussendoor, in 2015, werd hij nog eenmaal uitgeleend aan zijn vorige club Puskás. In januari 2016 maakte hij een transfer naar Werder Bremen, waar hij zijn handtekening zette onder een verbintenis tot de zomer van 2019.[1] In een half jaar tijd speelde hij zes competitiewedstrijden voor Werder. In de daaropvolgende zomer werd hij voor de duur van één seizoen op huurbasis bij SV Darmstadt 98 gestald.[2] Na een half jaar keerde Kleinheisler terug naar Werder, dat hem direct opnieuw verhuurde, nu aan Ferencváros.[3] Na een verhuur aan FC Astana, nam die club hem over. Vanaf begin 2019 komt hij uit voor NK Osijek.
Kleinheisler maakte zijn debuut in het Hongaars voetbalelftal op 12 november 2015, toen met 0–1 gewonnen werd van Noorwegen. Kleinheisler mocht van bondscoach Bernd Storck in de basisopstelling starten. Na zesentwintig minuten tekende de middenvelder voor de enige treffer van de wedstrijd en achttien minuten voor het einde van de wedstrijd werd hij gewisseld voor Ádám Nagy.[5] Met Hongarije nam Kleinheisler in juni 2016 deel aan het Europees kampioenschap voetbal 2016. Hongarije werd in de achtste finale uitgeschakeld door België (0–4), nadat het in de groepsfase als winnaar boven IJsland en Portugal was geëindigd. Kleinheisler kwam op het EK in twee wedstrijden in actie. Tegen Oostenrijk begon hij in de basis en verving Zoltán Stieber hem elf minuten voor tijd en tegen IJsland liet Storck hem de gehele wedstrijd spelen. Zijn toenmalige teamgenoten Theodor Gebre Selassie (Tsjechië) en Zlatko Junuzović (Oostenrijk) deden ook mee aan het EK.