Kazik mieszkał w Łodzi na ulicy Wrześniowej 26 (obecna Powstańców Wielkopolskich), w dzielnicy Żubardź. Dzielił mieszkanie z Henrykiem - swoim bratem, i jego żoną, a wkrótce także z ich pierwszym synem. Woleli taki układ niż jakiś samodzielny pokoik, który mógł Kazikowi wynająć ŁKS. Łódzki klub nie spieszył się, z taką decyzją z dwóch powodów. Pierwszy stanowił fakt iż, po upływie dyskwalifikacji stanie się zawodnikiem Arki Gdynia (wg obowiązujących wtedy przepisów), co wyszło na jaw dopiero po przybyciu do Łodzi. Drugi to dyskwalifikacja nałożona przez PZPN, która pozwalała jedynie na uczestniczenie w treningach, trudno więc było określić przydatność do pierwszego zespołu. Z czasem w mieszkaniu na Wrześnieńskiej zaczęli pojawiać się wysłannicy z Arki, którzy namawiali Deynę do powrotu na Wybrzeże. Deyna jednak zgodzić się nie chciał. Dla działaczy ŁKS-u najazdy Gdynian nie stanowiły zagrożenia. To co najgorsze dla władców z al. Unii dopiero miało nastąpić. O Deynę upomniała się armia. Z początku nie wyglądało to groźnie, ponieważ zgłosiły się o niego Zawisza Bydgoszcz i Legia Warszawa, które toczyły walkę o zawodnika między sobą, co wprowadziło wiele bałaganu do tego stopnia, że trzeba było ponownie ustalać miejsce pobytu poborowego. Bogu ducha winien Deyna nagle stał się człowiekiem poszukiwanym przez wojsko i milicję, za uchylanie się od służby wojskowej. Kazik noce zaczął spędzać w domu, zaś w czasie treningów, pod stadionem wystawiano tajniaków, którzy wypatrywali czy nie przyjechała przypadkiem milicja. Zdawało to egzamin na dosyć długi czas, aż w końcu któregoś dnia do domu przyjechał dzielnicowy. Jak się później okazało po to, by namówić Deynę na przejście do "Białej Gwiazdy", ale akcja zakończyła się fiaskiem, a Kazik spędził noc w areszcie. Rano następnego dnia sprawą zajęły się władze wojskowe. Po kilku miesiącach spędzonych w Łodzi na treningach i zabawach w chowanego z patrolami, Deynie skończył się okres zawieszenia. Mógł zagrać w oficjalnym meczu, bez obaw, że skończy się to następną kara. Zadebiutował w drugim zespole ŁKS-u, który wygrał z Włókniarzem Białystok 7:2. Kazik strzelił pięć goli!

8 października 1966 roku, prawie rok po debiucie w reprezentacji juniorów, postanowiono sprawdzić Deynę w lepszym towarzystwie. Kazik zagrał po raz pierwszy w I lidze. ŁKS grał u siebie z Górnikiem i zremisował 0:0. Debiut wypadł przeciętnie, biorąc pod uwagę późniejsze osiągnięcia. Kiedy jego nazwisko pojawiło się w sprawozdaniach obok tych najsłynniejszych, w Legii potraktowano fakt prestiżowo. ŁKS miał pecha, nastąpił okres jesiennego poboru, wkrótce po debiucie trzej piłkarze otrzymali karty powołania. Na liście znaleźli się: Kazimierz Deyna, Zdzisław Kostrzewiński i Edward Studniorz. Na początku wybuchła fala krytyki ze stron łódzkich działaczy, później doszło do negocjacji, w wyniku czego Legia miała wziąć tylko jednego zawodnika. Dwóm pozostałym służbę wojskową odroczono. Dziś, po tylu latach, twierdzi się, że Legii było dokładnie wszystko jedno, który piłkarz przeniesie się do Warszawy. Żaden nie należał do asów i nawet nie było pewności, czy w ogóle trafi do pierwszej jedenastki wojskowych (tak jak w późniejszych latach, w przypadku Henryka Kasperczaka, ale to już inna historia). Decyzję oddano więc w ręce działaczy z Łodzi. Ci zastanawiali się dość długo, a zdecydowali się w końcu na pozostanie Kostrzewińskiego i Studniorza, na ich występy liczono bardziej. Deyna miał zaledwie jeden mecz w I lidze, a to stanowczo za mało do określenia przydatności i możliwości gracza. Tak więc ddali Kazika, który tego dnia wydawał się im najsłabszy. W ten sposób Kazimierz Deyna, kilka dni po debiucie w ekstraklasie, wyjechał do stolicy.

Nazywali go "Kaka". Sam nie wiedział dlaczego. Jedna z wersji mówi, że to od rodzaju strzałów, z których Deyna zasłynął. "Kaka", czyli "kaczka" - strzał, po którym piłka uderza w ziemię przed bramką, myląc tym obrońców i, przede wszystkim, bramkarza. Piłka przez niego kopnięta zachowywała się jak kamień, rzucony płasko na wodę, który, nim ostatecznie się w niej zagłębi, uderzy kilkakrotnie o powierzchnię. Tę wersję należałoby jednak odrzucić, ponieważ "Kaka" mówiono na Kazika jeszcze nim zaczął regularnie, w niemal każdym meczu imponować swoimi strzałami. Władysław Stachurski, powiedział kiedyś, że określenie wzięło się od sposobu chodzenia Deyny. Był wysoki, miał metr osiemdziesiąt wzrostu, a chodząc, stawiał nogi do środka, co sprawiało, że "kołysał się jak kaczka". Jak się później okazało przydomek stał się, nieodłączną częścią nazwiska. Szybko stał się gwiazdą warszawskiej publiczności. Genialność Deyny polegała na tym, że wielu ludzi nie rozumiało jego gry, a najbardziej jej nie rozumiano na Śląsku. Jak grał? Nie trzeba słów. Można jego grę analizować na wiele sposobów, a i tak się jej nie zrozumie, bo geniusz zrozumieć niełatwo. Deyna nie był bystry ani rozmowny, unikał rozgłosu, a udzielanie wywiadów stanowiło dla niego katorgę. Nie umiał opisać najprostszej akcji, którą przeprowadził, ale gdy wychodził na boisko, przerastał o kilka poziomów inteligentnych absolwentów wyższych uczelni. Deyna był pupilem trenera Vejvody. Rola czeskiego trenera w rozwoju Kazika jest chyba większa niż wtedy myślano i uważa się dziś. Kiedy trzeba - krzyknął, innym razem pochwalił. Ich rozmowy w klubie w cztery oczy toczyły się niemal codziennie i dotyczyły rożnych spraw. Od szkoleniowych począwszy, a na osobistych i wręcz intymnych skończywszy. Kazimierz Deyna przyszedł do Legii w połowie października 1966 roku. Nie wiedział jeszcze, że spędzi w niej dwanaście lat. Najlepszych dwanaście z czterdziestu dwóch. Zaczynał nowe życie. Pierwsze trzy tygodnie spędził w jednostce samochodowej, znajdującej się niedaleko stadionu Wojska Polskiego, przy ulicy Podchorążych. Po niecałym miesiącu przeniósł się do Ośrodka Sportowego, mieszczącego się wtedy na rogu ulic Łazienkowskiej i Czerniakowskiej, nadal jednak podstawowym ubraniem Kazika był mundur szeregowca. Po przysiędze zaprowadzono go na trening pierwszej drużyny. Minęło pięć kolejnych dni i 20 listopada 1966 roku zobaczono go po raz pierwszy w barwach Legii na Łazienkowskiej, w meczu ligowym z Ruchem Chorzów. Przyszedł do Legii i to jakiej, do Legii, która była naszpikowana gwiazdami, takimi jak: Brychyczy, Blaut, Grotyński, Żmijewski, młody Gadocha (później uznany za najlepszego skrzydłowego na świecie). Początki go przeraziły. Kiedy zjawił się na Łazienkowskiej, rozgrywki miały się ku końcowi, w lidze wiodło się legionistom niezbyt dobrze. Jesienią 1966 roku nie wygrali ani jednego z siedmiu spotkań w Warszawie i zakończyli ten rok na dziesiątym miejscu w tabeli. W ekstraklasie grało wtedy czternaście drużyn. Przez pierwsze trzy miesiące w parze z Deyną ćwiczył Jacek Gmoch. Wybrał sobie Kazika, widząc w nim prawdopodobnie kogoś, z kim może rywalizować. Pomysł stworzenia stałej pary z Gmocha i Kazika okazał znakomity i dla nich obydwu, i dla drużyny. Z polecenia trenera Gmoch stał się opiekunem wchodzącej do drużyny "Kaki" nie tylko na boisku, ale i poza nim. W dość szybkim czasie polecenie stało się przyjemnością, do tego stopnia, że trudno im było się rozstawać po treningach. Ich wspólne treningi prowadziły do ciągłej rywalizacji. Najważniejszy dla kariery "Kaki" był chyba pierwszy mecz w barwach Legii. Z ŁKS-u do Legii przychodził jako napastnik i w napadzie wystawiono go w debiucie przeciwko Ruchowi. Vejvoda popatrzył jak chłopak gra, by po spotkaniu wypowiedzieć w szatni zdanie: "Kaziu, ty jseś rozeny zaloźnik" - jesteś urodzonym pomocnikiem. Od tej pory Deyna stał się graczem drugiej linii, mając w niej za partnerów Bernarda Blauta, a później Lucjana Brychyczego. Zajął miejsce Wiesława Korzeniwskiego, w tamtych czasach uchodzącego za największy talent Warszawy. 28 maja 1967r. Legia pokonała we Wrocławiu Śląsk 3:1, a Kazimierz Deyna strzelił wszystkie trzy bramki w ciągu połówki pierwszej połowy - to był jego pierwszy hat-trick w lidze. Ligowa jesień w 1967 stanowiła popis Legii, która w dwunastu meczach poniosła tylko jedną porażkę, z Górnikiem Zabrze. Był to też pierwszy sezon, w którym Kazimierz Deyna występował stale w drugiej linii. Po kontuzji kończącej karierę Jacka Gmocha w sierpniu 1968 roku i odejściu Henryka Apostela, ukształtowała się jedenastka, która później zdobyła pierwszy tytuł Mistrza Polski od 1956 roku. Drużyna była zgrana, a role w niej podzielone. Deyna był najmłodszy, a mimo to najczęściej decydował o grze i o wyniku. Zmieniła się drużyna, zmieniło się również życie Kazimierza Deyny. Do października 1968 roku pełnił zasadniczą służbę wojskową. Dopóki służył w wojsku, nie musiał myśleć o samodzielnym życiu. Wszystko podawano mu pod nos, na brak pieniędzy nie narzekał. Jeździł wtedy często do Starogardu, po każdym takim pobycie w kieszeniach rodzeństwa lub ich dzieci zostawały jakieś złotówki. Im grał częściej i lepiej, tym było ich więcej. W tym czasie miał też kilka propozycji z innych klubów. Jednak Legia już dobrze wiedziała jaki skarb jej się trafił i nie zamierzała się go pozbywać. Ponieważ nie bardzo wiedziała co mu zaproponować i jak potraktować ŁKS, którego zawodnikiem Deyna stawał się automatycznie w dniu zakończenia służby wojskowej, dokonano więc prostego zabiegu. Kiedy dni odejścia zbliżały się milowymi krokami, Deyna dostał rozkaz z Ministerstwa Obrony Narodowej. Treść pisma oznajmiała, że Kazimierz Deyna zostaje przeniesiony do Marynarki Wojennej, a jednocześnie mianowany zostaje na stopień "Bosmanmata". Ponieważ sam Kazik nie bardzo mógł się zdecydować jak pokierować swoimi krokami - list przyjął z ulgą.

Pierwsze samodzielne mieszkanie jakie otrzymał od Legii, to kawalerka przy ulicy Płockiej na Woli. Deyna spędził tam kilka miesięcy. Było z tym trochę problemów, bowiem lokator lubił korzystać z życia. Mieszkanie stało się i kawalerką, i garsonierą w potocznym rozumieniu. Deyna miał niewiele ponad 20 lat i wszelkie prawa do poznawania świata. Czasami nawet nieco z tym przesadzał. Zdarzało się, że nawet w tym pierwszym okresie gry w Legii, kiedy należało szczególnie walczyć o miejsce, Kazik zapominał o swoich obowiązkach. Czasami trzeba go było szukać po całej Warszawie. Raz spóźnił się na zbiórkę przed wyjazdem na mecz do Krakowa, innym razem w ogóle nie pojechał na obóz do Jugosławii. Z tych samych powodów (a była to jego pierwsza zima w Legii), trenował przez dwa tygodnie w błocie po kostki z drugą drużyną, na bocznym boisku, co dało mu trochę do myślenia. Na jakiś czas przynajmniej. Nigdy nie palił, nie pił, uwielbiał tylko "bliskie kontakty trzeciego stopnia" z kobietami. Z wzajemnością zresztą. Któregoś lutowego dnia 1967 roku, pod pensjonat w Szklarskiej Porębie, w którym przebywali legioniści, przyjechała dziewczyna z walizką. Najpierw upewniła się czy aby dobrze trafiła, po czym oznajmiła: - "Ja do pana Deyny. Jestem zaproszona". Pana Deynę oczywiście poinformowano o miłej wizycie, ale pana trenera również. Vejvoda zaprosił go do swojego pokoju i z cierpliwością, jaka cechuje ojca strofującego dziecko powiedział: - "Kaziu, skoro panienkę zaprosiłeś, to nie wypada się nią nie zająć. Wynajmij jej pokój na tę noc, zaproś na herbatę, bo dziewczyna wygląda na zziębniętą, a potem idź na stację i kup jej bilet powrotny do Warszawy. Koniecznie na jutro rano. Ale pożegnaj się z nią już dziś". Takie to były początki życia Kazika w wielkim mieście. Kiedy kończył się dodatkowy rok służby, o istnieniu Deyny przypomnieli sobie działacze z al. Unii, którzy dotychczas w ogóle się nim nie interesowali. Na tyle uraziło to Kazika, iż postanowił zostać podoficerem zawodowym. Łódzki klub stracił w tym momencie szansę na pieniądze, o jakich myślał. Musiał zadowolić się tylko tymi, jakie w takich przypadkach określał regulamin.