Kleinheisler fontos góllal debütált a válogatottban az Eb-pótselejtezőn

2013. július 28-án kapott először lehetőséget a magyar élvonalban az akkor 19 éves Kleinheisler László, és a Haladás ellen 2-0-ra megnyert találkozó első gólját, a 25. percben ő szerezte. A nagy hőségben lejátszott mérkőzés 23. percében a játékvezető ivószünetet rendelt el, közvetlenül ezután "Scholes" becenévre hallgató játékos a jobb szélről cselezett középre, majd 15 méterről, jobb külsővel, szép mozdulattal talált a kapuba.

Két és fél évvel később, 2015. november 12-én, csütörtök este Kleinheisler a felnőtt válogatottban is bemutatkozhatott. Debütálása hasonlóan jól sikerült, mint az élvonalban. Norvégiában, a találkozó 26. percében szépen vette át Elek Ákos labdáját, majd bal lábbal, 15 méterről lőtt a kapuba. Mint később kiderült, gólja győzelmet ért, és amennyiben vasárnap a nemzeti együttesnek sikerül kiharcolni a továbbjutást, úgy elmondható, hogy az elmúlt 30 év egyik legfontosabb magyar találata volt.