Legia Warszawa W przerwie zimowej sezonu 1991–1992 Zieliński dołączył do przeżywającego kryzys zespołu Legii. Warszawska drużyna, mająca za sobą udział w półfinale Pucharu Zdobywców Pucharów rok wcześniej, tym razem walczyła o miejsce w środku tabeli. Zieliński pierwszy raz w koszulce Legii wystąpił 14 marca 1992 w wygranym 2:1 wyjazdowym meczu z Hutnikiem Kraków. Szybko zdobył zaufanie trenera Krzysztofa Etmanowicza i stał się podstawowym graczem zespołu.
Na początku sezonu 1992–1993 Etmanowicza zastąpił były trener olimpijskiej reprezentacji Polski i zdobywca srebrnego medalu na Igrzyskach w Barcelonie Janusz Wójcik, który również zaufał Zielińskiemu. W warszawskim zespole spotkał także Leszka Pisza, z którym kilka lat wcześniej występował w Igloopolu. Sezon 1992–1993 zakończył się dla Legii nieszczęśliwie – drużyna zajęła pierwsze miejsce, jednak po weryfikacji wyników ostatniej kolejki władze PZPN postanowiły odebrać jej tytuł mistrzowski.