Zespół zakończył sezon 1966/1967 na czwartej pozycji w Ekstraklasie.

W drugim sezonie w barwach Legii, Deyna zdobył wicemistrzostwo Polski. Wystąpił we wszystkich 26 meczach ligowych, zdobywając 12 bramek.

W sezonie ligowym 1968/1969, gdy trenerem był Edmund Zientara, Legia zdobyła mistrzostwo Polski (na finiszu rozgrywek pięć punktów przewagi nad Ruchem Chorzów). W sezonie tym Deyna wystąpił 23 razy w zespole mistrza Polski, grając łącznie 1994 minuty.

Kiedy dodatkowy rok służby wojskowej dobiegał końca, Deyna za namową Lucjana Brychczego i Bernarda Blauta zdecydował się pozostać w Legii jako podoficer zawodowy. Zgodnie z obowiązującymi wówczas przepisami zarówno zawodnik, jak i ŁKS otrzymali po 100 tysięcy złotych – klub w ramach ekwiwalentu za wyszkolenie, a Deyna jako premię za pozostanie w Legii.

W sezonie 1969/1970 Legia po raz drugi z rzędu zdobyła mistrzostwo Polski. Deyna wystąpił w 23 spotkaniach, strzelając 5 goli. W Pucharze Mistrzów warszawski zespół doszedł do półfinału rozgrywek, w którym uległ Feyenoordowi w dwumeczu 0:2.

Sezon 1970/1971 Legia z Kazimierzem Deyną w składzie skończyła na drugim miejscu.