Tenerife CD Następnie zaakceptował propozycję, która napłynęła od byłego szkoleniowca Borussii Mönchengladbachm, Juppa Heynckesa, który został trenerem hiszpańskiego CD Tenerife. Lienen został jego asystentem, a klub zajął wyśmienite piąte miejsce na mecie sezonu 1994–1995. Następny rok nie był już równie spektakularny, ale solidny i zakończony na dziesiątej lokacie. Heynckes następnie odszedł do Realu Madryt, a Lienen doszedł do wniosku, że jego czas na Półwyspie Iberyjskim minął i postanowił wrócić do Niemiec i rozpocząć samodzielną pracę w Hansie Rostock.
Powrót do kraju Sezon 1997–1998 okazał się sporym sukcesem i niespodzianką. Medialnie skazywany na niepowodzenie klub zajął bardzo wysokie szóste miejsce, co pozwoliło na większe aspiracje. Kilka miesięcy później Hansa walczyła już o uniknięcie degradacji. Lienen zapłacił za dotkliwą porażkę z Bayernem 0:4 przed własną publicznością i pożegnał się z posadą w marcu 1999 roku. Bez niego zespół poradził sobie i uniknął pewnego spadku do 2. Bundesligi. Spadkowicz FC Köln chętnie przystał na warunki Lienena i podpisał z nim kontrakt. Ten przywrócił zasłużony zespół do najwyższej klasy rozgrywkowej. W sezonie 2000–2001 zespół zajął komfortowe dziesiąte miejsce w tabeli, ale kolejny – jak zwykle już dla Lienena – nie był równie udany i zespół spadł.