Zatoka Wielorybia posiada dobre warunki naturalne sprzyjające założeniu przystani. Wody zatoki bogate wplankton przyciągaływieloryby. Wkrótce pojawili się teżwielorybnicy. Przystań stanowiła też ważny punkt na szlaku morskim wokół Afryki. Wszystko to wyjaśnia skomplikowaną historię tego miejsca i spory wokół jego przynależności politycznej.
Pierwszym Europejczykiem w Walvis Bay byłportugalski żeglarzBartolomeu Dias, który przypłynął tu 8 grudnia 1487 na pokładzie statkuSão Cristovão podczas wyprawy w poszukiwaniu nowej drogi doIndii. Odkrytej przez siebie zatoce nadał nazwę „O Golfo de Santa Maria da Conceição”. Jednakże Portugalczycy nie wysuwali żadnych roszczeń terytorialnych wobec tego obszaru.
Dopiero w 1840 większe zainteresowanie tym obszarem wykazałaWielka Brytania, która ostatecznie opanowała Walvis Bay i okolice w 1878. W 1884 włączyła go doKolonii Przylądkowej (Cape Colony). Zajmując Walvis Bay, Brytyjczycy kierowali się dwiema przesłankami: zabezpieczeniem przystani dla brytyjskich statków na szlaku dookołaPrzylądka Dobrej Nadziei oraz zachowaniem wpływów w obszarze niemieckiej ekspansji kolonialnej. W 1910 obszar Walvis Bay wszedł w składZwiązku Południowej Afryki. W 1911 doszło do sporu wokół granicenklawy Walvis Bay z terytoriumNiemieckiej Afryki Południowo-Zachodniej. Ostatecznie po brytyjsko-niemieckich uzgodnieniach jej powierzchnia wynosiła wówczas 1124 km².
W 1915 południowoafrykańskie wojska wyparły Niemców i przyłączyły Walvis Bay do kontrolowanej przez nichAfryki Południowo-Zachodniej. Wkrótce południowoafrykańską kontrolę nad tym terytorium potwierdziłaLiga Narodów. W 1921 uchylono stan wojenny i przywrócono rządy cywilne, a Walvis Bay stało się integralną częścią wspomnianego terytorium. W1971, wraz z pojawiającymi się żądaniami niepodległości ze strony Afryki Południowo-Zachodniej, RPA podjęło decyzję o przekazaniu kontroli nad Walvis Bay władzomProwincji Przylądkowej. W 1977 RPA, obawiając się utraty Walvis Bay po przejęciu władzy przez niepodległościowy ruchSWAPO, po raz kolejny potwierdziło swoje żądania zachowania kontroli nad tym terytorium.
W 1978Rada Bezpieczeństwa Narodów Zjednoczonych wydała rezolucję, na mocy której Walvis Bay wróciło pod administrację rządu wWindhuk, jednocześnie otwierając dwustronne negocjacje w sprawie przyszłego politycznego statusu Walvis Bay. Ostatecznie, gdy w 1990 Afryka Południowo-Zachodnia uzyskała niepodległość jakoNamibia, obszar Walvis Bay pozostał jeszcze pod kontrolą południowoafrykańską. Dopiero w 1994 pod naciskiem lokalnych stowarzyszeń biznesowych RPA zgodziła się na przekazanie miasta Namibii.
