Jest to jeden z większych przedstawicieli rodziny teidowatych (Teiidae). Dorosłe osobniki mogą osiągać nawet 100 -130 cm dł i ważyć do 4 kilogramów. Jest to masywna jaszczurka przypominająca na pierwszy rzut oka warany, niespokrewniona jednak z nimi. Rodzina teidowatych jest znacznie bliższa jaszczurkom właściwym (Lacertidae), jednakże na skutek konwergencji ewolucyjnej upodobniły się morfologicznie do waranów i zajmują ich niszę ekologiczną w Ameryce Południowej.
Ubarwienie teju czarnoplamego jest bardzo zróżnicowane, różne u poszczególnych populacji a nawet w obrębie jednej populacji występuje duża zmienność kolorystyczna. Zasadniczo wzór ubarwienia stanowi mozaika różnorodnej wielkości jasnych plam (białych, kremowych, żółtawych lub lekko pomarańczowych) na ciemnym (czarnym lub brunatnym) tle. U niektórych osobników jasne plamy zlewają się w pręgi. Spód ciała jest jasny, ale widoczny jest na nim deseń z ciemniejszych, drobnych cętek. Łuski pokrywające ciało są granulkowate, pozbawione kilu. Na głowie łuski są silnie powiększony i tworzą gładkie płytki. Łuski na ogonie są płaskie, prostokątne w kształcie i ułożone pierścieniowato. Kończyny są masywne i bardzo silnie umięśnione.Palce zakończone bardzo silnymi pazurami. Ogon jest owalny w przekroju, silny, ułatwia utrzymywanie równowagi podczas wspinaczki oraz służy do obrony.
Zmysły doskonale rozwinięte. Bardzo dobry wzrok umożliwiający widzenie kolorów. Dobry słuch. Węch świetnie rozwinięty. Język długi, ruchliwy i rozdwojony na końcu. Uzębienie heterodontyczne, zróżnicowane - przednie zęby drobne i niewielkie, stożkowate. Zęby znajdujące się dalszej części szczęk duże, ostre i zakrzywione. Tylne zęby masywne, szerokie z zaczątkami guzków - służą do miażdżenia twardej zdobyczy.