Karierę zaczynał w kameruńskim klubie o nazwie Mineduc. Następnie trafił do Unionu Duala. W 2000 roku wyjechał z ojczyzny do Szwajcarii, by bronić barw Neuchâtelu Xamax. Po dwóch sezonach przeszedł do FC Basel. To tam wypłynął na szerokie wody Ligi Mistrzów, a znakomitymi występami, m.in. przeciwko Manchesterowi United zwrócił na siebie uwagę czołowych klubów Europy. W 2004 roku trafił do Tottenhamu Hotspur za kwotę 4 500 000 euro. Debiutował już w pierwszej kolejce Premier League, w meczu z Liverpoolem. Wszedł na boisko w 70 minucie, a mecz zakończył się rezultatem 1:1. Po sezonie parol na lewego obrońcę reprezentacji Kamerunu zagiął niemiecki Hamburger SV i za 2 500 000 euro udało się sfinalizować transfer. Dotychczas największym sukcesem Atouby w barwach HSV jest zajęcie 3 miejsca w sezonie 2006/2007, a także wcześniejsze występy w Lidze Mistrzów i Pucharze UEFA w którym HSV odpadł w 1/8 finału, przegrywając z Rapidem Bukareszt. W 2009 Atouba przeszedł do Ajaksu Amsterdam. Następnie grał w UD Las Palmas, gdzie w 2014 roku zakończył karierę.