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 kwam hij uit voor NK Osijek waar hij tot begin 2023 zou spelen. Op 19 januari 2023 tekende hij een contract bij Panathinaikos FC.[4] Minder dan een jaar later, op 2 januari 2024 werd Kleinheisler uitgeleend aan Hajduk Split.
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.[6] 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.
Kleinheisler werd op 14 mei 2024 door bondscoach Marco Rossi opgenomen in de Hongaarse selectie voor het EK 2024 in Duitsland.[7] Hongarije werd in de groepsfase uitgeschakeld na nederlagen tegen Zwitserland (1–3) en Duitsland (2–0) en een overwinning tegen Schotland (0–1). Kleinheisler kwam in actie tegen Zwitserland en Duitsland.