Tarkan ikinci albümünün hazırlık aşamasında, Türkiye'nin en önemli seslerinden Sezen Aksu ile tanıştı. Müzikal anlamda ilk kez buluşan iki sanatçının çalışmaları sonucunda "Şıkıdım" şarkısı ikinci albüme dahil oldu.

1995 yılında çıkan ikinci albümü "Aacayipsin" ile Türkiye ve Avrupa'da tam 74 konser verdi. Bu konserlerin 25 tanesi, o ana kadar ulusal çapta gerçekleştirilen en büyük sponsorlu turne kapsamında, Tarkan'ı Türkiye'nin farklı illerinde yaklaşık 750 bin seyirci ile buluşan stadyum konserleriydi. Bunlarla birlikte Tarkan çok önemli bir başarıya daha imzasını attı ve albüm 2.5 milyona yakın sattı.

Bunun ardından dil eğitimi almak üzere New York'a gitti. Bu dönemde tanıştığı Ahmet Ertegün ve Atlantic Records'la yeni projeler üzerinde çalışmaya başladı.

1994 - 1997 yılları arasında İsviçre, Hollanda ve Almanya'da toplam 12 şehri kapsayan 3 büyük Avrupa turnesine çıktı. 1995 yılında New York Palladium'da verdiği konser, Türkiye'de canlı yayınlandı.

Tarkan, 1997 yılının Temmuz ayında, üçüncü albümü "Ölürüm Sana" ile müzik dünyasında yine bir Sezen Aksu parçasıyla büyük bir çıkış yaptı. Bu albüm için yaklaşık 2 yıl boyunca hazırlanan Tarkan, Sezen Aksu’nun da katkılarıyla istenilen başarıya ulaştı ve ilk kez uluslararası müzik sektöründe kendini tanıttı. Üçüncü albümüyle tüm dünyaya sesini duyuran Tarkan’ın bu albümü 3.5 milyon sattı.

Tarkan bu başarının ardından hiç ara vermeden konserlere başladı. İstanbul, Ankara, İzmir, Adana ve Antalya’da verilen stadyum konserlerini, 10 ili daha kapsayan bir Türkiye turnesi izledi.

Güney Amerika'da verdiği konserlerde, seyirci Tarkan'a şarkılarında eşlik ederek büyük bir coşkuyla izledi.

Tarkan, yine 1997'nin Aralık ayında bu kez 17 ayrı şehirde 18 konserden oluşan yeni bir Avrupa turnesine çıktı.

Bu sırada, sanatçılarla yapılan çalışmaların albüm ve kliplerle sınırlı kalmaması vizyonu ve kendine ait bir müzik prodüksiyon şirketine sahip olma hedefi, Hitt Müzik projesinin çıkış noktası oldu.

1998'de ise İstanbul Plak'ın, "Ölürüm Sana" albümünün Avrupa'daki lisans haklarını ünlü Fransız firması Polgram'a devretmesi ile Tarkan'ın Avrupa'daki tanınırlığı önemli ölçüde arttı.

Böylece Tarkan, başta "Şımarık" single'ı olmak üzere, "Ölürüm Sana" albümü ile tüm Avrupa’ya Türkçe şarkı söyletmeyi başardı. Ve yine aynı albümle, Meksika'da Platin, Fransa, Hollanda, Almanya, Belçika, Lüksemburg, İsveç ve Kolombiya'da da Altın Plak ödülleri kazandı
 

1999 yılının baharında başlayan ve Almanya, Fransa, İngiltere, Belçika, Hollanda, Danimarka, Avusturya, Portekiz, Ukrayna, Fas, Avustralya ve Tunus gibi pek çok farklı ülkeyi kapsayan bir başka turne ise, aynı yılın yaz aylarında son buldu.

2000 yılının Şubat ayında askerliğini yapmak üzere Türkiye'ye dönen Tarkan, teslim olmadan hemen önce 14 Ocak'ta, 17 Ağustos depreminde zarar görmüş depremzedeler yararına İstanbul Mydonose Showland'de Türkiye’de ilk kez özel bir ses ve ışık sisteminin kullanıldığı bir konser verdi.

Dünya çapında bir sanatçı olmasıyla, sorumluluğunu daha da artan Tarkan, askerlik dönüşünde yeni albümünün çalışmalarına iyice hız verdi. 2 yıl süren titiz çalışmaların ürünü olan "Karma" albümü, Amerika, Fransa ve Mısır'daki stüdyolarda kaydedildi ve Mayıs 2001'de Kuzu Kuzu single'ı 5 değişik versiyonuyla tüm müzik marketlere sunuldu.