Taki zalążek popularności skłonił go do uformowania zespołu. Rzecz działa się w roku 1979, a w grupie o nazwie Escape występował u boku pary gitarzystów. W garażu Dave’a członkowie wykonywali utwory Black Sabbath, Led Zeppelin i AC/DC. W tym czasie w szkole nie szło mu najlepiej, przez co wkrótce przeniósł się do South Gate High School, gdzie poznał wokalistę, będącym przyszłym członkiem jego zespołu. Grupa zmieniła nazwę na Sabotage, tworzyła covery piosenek, jednak nie zrobiła większego wrażenia na publiczności. Niedługo potem jego rodzice zorientowali się, że Dave poświęca się bez pamięci muzyce. Namówili go na rzucenie szkoły i znalezienie pracy. Wkrótce zatrudnił się na stanowisku dostawcy pizzy, dzięki czemu spłacił dług u ojca (pieniędzy potrzebował na zakupienie zestawu TAMA Swingstar oraz Zaiste Rude Cymbals).
W tym czasie Dave usłyszał o lokalnym gitarzyście Kerrym Kingu. Przedstawił mu się oraz zaproponował współpracę. Okazało się, że King poszukuje perkusisty do swojego zespołu – Slayer – co było dla Lombardo gwiazdką z nieba. Wraz z zespołem Dave koncertował we wczesnych latach osiemdziesiątych, promując debiutancki album „Show No Mercy”. W tym czasie wpływ na jego muzykę miał perkusista Gene Hoglan, związany ze Slayer. W roku 1986, podczas trasy promującej „Reign in Pain” Lombardo zrezygnował z dalszej współpracy z zespołem, ponieważ nie otrzymywał stałej pensji. Na jego miejsce Slayer przyjęło Tony’ego Scaglione. Rozłąka z zespołem nie trwała jednak długo. Wkrótce, 19 lipca 1986 roku Dave poślubił Teresę, która nakłoniła go do powrotu. Jednak i ponowienie współpracy nie trwało długo… Co prawda Lombardo nagrał u boku zespołu „South of Heaven” oraz „Seasons in the Abbys”, lecz w roku 1992 w wyniku konfliktu z członkami grupy.