W 1966 r. w klubie przy Łazienkowskiej pojawił się 19-letni, małomówny chłopak ze Starogardu Gdańskiego. Miał już za sobą występy w juniorskich reprezentacjach kraju i uchodził za wielki talent. Nie wszyscy jednak byli do niego przekonani, a bardziej doświadczonych legionistów irytował sposób gry przybysza.

„Miałem łatwość nawiązywania kontaktów z ludźmi – wspominał skrzydłowy, Janusz Żmijewski – dlatego jako jeden z nielicznych w drużynie potrafiłem dotrzeć do Kazika, chociaż, jak pamiętam, w początkowej fazie jego gry w Legii nie najlepiej układała się nam współpraca na boisku. Ja lubiłem szybką piłkę, a on, kręcąc te swoje kółeczka, powodował, że biegałem na próżno. Nieraz to mnie wkurzało i mówiłem trenerowi Vejvodzie, że nie potrafię z nim grać. Wtedy trener mi tłumaczył: »Januszek, zobaczysz, on będzie najlepszy z was«. I tak faktycznie było”.

Czeski trener Legii był znakomitym fachowcem i dobrze wiedział, że Kazimierz Deyna ma wszelkie szanse na to, aby zostać najlepszym pomocnikiem w polskiej lidze. Nie tylko zresztą w lidze, ponieważ piłkarz z Pomorza zapowiadał się na zawodnika światowego formatu. Na boisku widział wszystko, dysponował znakomitymi techniką i strzałem. Dobrych zawodników w Polsce było wielu, ale takiego piłkarza jak Deyna nad Wisłą jeszcze nie widziano.

„Nie spotkałem w Polsce drugiego piłkarza – potwierdzał Zbigniew Boniek – który tak dobrze czytał grę i widział, co dzieje się lub za chwilę będzie się działo na boisku. Poza tym Deyna zawsze był graczem, na którego przeciwnicy zwracali całą uwagę, więc jego partnerzy mieli sporo swobody, dużo miejsca do gry. On bez przerwy uwikłany w potyczki z pilnującymi go »plastrami« i posyłający celne podania, ty zaś luźny, swobodny i w dodatku piłki spadają ci tuż przed nosem… Czy można sobie wyobrazić większy komfort gry?”.

Koledzy z Legii szybko zaczęli wysoko cenić Deynę, chociaż Kazimierz właściwie nigdy się z nimi nie integrował. Był człowiekiem zamkniętym w sobie, chadzał własnymi ścieżkami, miał też liczne słabości. Największą z nich było upodobanie do płci pięknej, bo Deynę można było wręcz uznać za seksoholika. I pomimo swojej małomówności raczej nie narzekał na brak powodzenia u kobiet.