W latach 1977–1980 dawał koncerty w całej Kalifornii, których podstawą były utwory napisane przez Ridgwaya jeszcze z czasów Acme Soundtracks. Dopiero w 1979, po podpisaniu kontraktu z wytwórnią IRS. Records, zespół wszedł do studia celem nagrania materiału gotowego do wypuszczenia na rynek muzyczny. W 1980 ukazało się pierwsze oficjalne wydawnictwo zespołu – Wall of Voodoo. Płyta zawierała 5 utworów, z czego jeden stał się pierwszym hitem grupy, jednak zbyt „słabym”, by wejść na listy Top 100 czy California Top 50. Był nim cover piosenki Johnny’ego Casha z 1968 roku pt. „Ring of Fire”. Interpretacja utworu była wyjątkowo ciekawa, bowiem wszystko zagrano w oparciu o jedną gitarę i syntezatory. W 1981 roku ukazał się pierwszy studyjny album grupy, Dark Continent. Zawierał on 11 utworów do których nagrania posłużył ten sam automat perkusyjny i dwa syntezatory. Album zebrał nawet dobre recenzje, szczególną uwagę zwracano na styl, w jakim utrzymana była płyta. Trzy utwory znajdujące się na albumie – „Red Light”, „Animal Day”, „Back in Flesh” oraz „Call Box” – grane były już wcześniej, od 1978 roku. Ten ostatni został wybrany jako jedyny singel z tej płyty. Drugim, jednak rzadko puszczanym przez stacje radiowe, singlem był utwór „Tse-Tse Fly”. Krótko po jej wydaniu Bruce Moreland odszedł z zespołu.