W latach 1958–1959 współpracował w Gdańsku z teatrem „Bim-Bom” i teatrzykiem/kabaretem „To-Tu”. W 1959 stworzył swój pierwszy kwartet Little Four. Jeszcze w tym samym roku rozpoczął współpracę z zespołem North Coast Combo oraz – jako klarnecista – z zespołem jazzu tradycyjnego Tralabomba Jazz Band. Występował też w orkiestrze gdańskiej Filharmonii Bałtyckiej.
W 1962 wystąpił po raz pierwszy na Jazz Jamboree i to w roli solisty – saksofonisty altowego w big bandzie Jana Tomaszewskiego. Na tej imprezie pojawiał się prawie przez 15 lat (prezentując się w różnych – głównie Andrzeja Trzaskowskiego – zespołach w latach 1962–1977). Autorskie trio zaprezentował w 1965 na festiwalu Jazz nad Odrą. W 1967 na Festiwalu Jazzowym w Wiedniu otrzymał I nagrodę indywidualną oraz medal, który wręczył mu Duke Ellington.
Nahorny sięgał po rozmaite muzyczne tworzywo: raz komponując balladę „Jej portret”, z drugiej strony realizował się w jazzowych zespołach Andrzeja Kurylewicza, Krzysztofa Sadowskiego, Andrzeja Trzaskowskiego, Jana Ptaszyna Wróblewskiego i Janusza Muniaka. Bywał też muzykiem rockowej grupy Breakout (nagrał z nimi trzy płyty), towarzyszył wokalistom – Mariannie Wróblewskiej, Łucji Prus, grupie Novi Singers oraz łączył jazz z muzyką poważną.