Majewski comenzó su carrera en los equipos locales "Gwiazda Bydgoszcz" y "Chemik Bydgoszcz", donde se formó como futbolista, luego debuta en primera división en 1977 en el Zawisza Bydgoszcz, luego pasó a uno de los grandes de Polonia el Legia Varsovia en 1979, donde hizo buenas campañas hasta 1984.