W 1990 rozpoczął pracę w Urzędzie Ochrony Państwa jako zastępca szefa. Pełnił funkcję szefa UOP od sierpnia 1990 do stycznia 1992 oraz od czerwca do lipca 1992, a od 5 czerwca 1992 do 11 lipca 1992 także sekretarza stanu w MSW. 11 lipca 1992 powołany na stanowisko ministra spraw wewnętrznych. Podał się do dymisji 22 grudnia 1995 po wyborze Aleksandra Kwaśniewskiego na prezydenta.
Dzień przed złożeniem dymisji udzielił w Sejmie informacji o rzekomej współpracy premiera Józefa Oleksego z radzieckimi i rosyjskimi służbami specjalnymi, co dało początek tzw. aferze Olina. Zarzuty przeciwko Józefowi Oleksemu nie zostały nigdy potwierdzone, a prokurator przedstawił Andrzejowi Milczanowskiemu zarzut ujawnienia tajemnicy państwowej. W lutym 2008 Sąd Okręgowy w Warszawie w pierwszej instancji uniewinnił go, uznając, że działał w stanie wyższej konieczności. W listopadzie 2008 Sąd Apelacyjny w Warszawie uchylił ten wyrok i sprawę przekazał do ponownego rozpatrzenia. W lipcu 2009 zapadł ponowny wyrok uniewinniający i umarzający postępowanie w odniesieniu do jednego z czynów z uwagi na znikomą społeczną szkodliwość.