Cavaliers zaczęli grać w NBA w 1970, w hali Cleveland Arena pod wodzą trenera Billa Fitcha, osiągając najgorszy wynik w lidze 15–67. Drużyna miała być budowana wokół numeru jeden draftu z roku 1971 Austina Carra, który był znakomitym strzelcem na uczelni Notre Dame, jednakże Carr doznał kontuzji nogi na początku kariery co nie pozwoliło mu zostać świetnym zawodnikiem zawodowym.
Następne sezony pokazały, że Cavaliers poprawili swoje wyniki na boisku dzięki grze utalentowanych zawodników takich jak Bingo Smith, Jim Chones, Jim Cleamons iDick Snyder. Cleveland poprawili swój wynik na 23–59 w sezonie 1971-72, w sezonie 1972-73 osiągnęli bilans 32–50 i osiągając mały krok wstecz w sezonie 1973-74kiedy uzyskali wynik 29–53. W 1974 Cavaliers przenieśli się do nowej hali Richfield Coliseum mieszczącej się na przedmieściach Cleveland. W sezonie 1974-75Cavaliers ukończyli sezon tuż za play-off z wynikiem 40–42.
W sezonie 1975-76 Cavaliers grali w składzie z Carrem, Smithem, Chonesem, Snyderem i nowym zawodnikiem Nate Thurmondem. Fitch pomógł zdobyć drużynie tytuł mistrza dywizji, kończąc sezon z wynikiem 49–33. Fitch zdobył wtedy tytuł trenera roku, wprowadzając Cavs do ich pierwszych play-off.
Cavs wygrali w pierwszej rundzie z Washington Bullets 4–3, dzięki wielu rzutom w ostatnich minutach. Mecze te były znane jako “Cud z Richfield”. Jednakże z powodu kontuzji Jima Chonesa Cavaliers przegrali w finale konferencji z Boston Celtics.
Cleveland wygrało 43 mecze w następnych dwóch sezonach (1976-77 i 1977-78), ale odpadali we wczesnych fazach play-off. Kiedy w sezonie 1978-79 uzyskali wynik 30–52, Fitch zrezygnował ze stanowiska trenera drużyny. W sezonie 1979-80, następcą Fitcha na stanowisku trenera został Stan Albeck, a Cavs osiągnęli wynik 37–45.
W 1980 nowym właścicielem drużyny został Ted Stepien. Nowy właściciel zatrudniał i zwalniał wielu trenerów, a także kupował słabych zawodników i wybierał nie najlepszych zawodników w drafcie.
Na początku swoich rządów Stepien chciał zmienić nazwę drużyny na "Ohio Cavaliers", tak aby mogła rozgrywać swoje mecze w Buffalo, Nowym Jorku i Pittsburgu. Stworzył także piosenkę bojową w rytm polki.
Chaos w drużynie Cavaliers odbijał się w wynikach na boisku. W sezonie 1980-81 (pierwszym Stepiena jako właściciela) drużyna uzyskała wynik 28–54, natomiast rok później wynik wynosił już 15–67. W sezonie 1981-82 drużyna przegrała 19 ostatnich meczów w sezonie, a na starcie nowego przegrała 5 pierwszych spotkań co jest najdłuższą serią przegranych spotkań z rzędu w historii NBA. Chociaż drużyna poprawiła swoje wyniki (23-59) na mecze do hali która mogła pomieścić więcej niż 20 000 przychodziło tylko 3900 kibiców. Stepien zagroził, że przeniesie drużynę do Toronto i zmieni jej nazwę na „Toronto Towers”, lecz bracia George i Gordon Gundodkupili drużynę i zdecydowali pozostawić drużynę w Cleveland (w 1993 Toronto będzie miało drużynę, która będzie się nazywać Toronto Raptors.) Dwa lata później Gundowie zmienili kolory koszulek z czerwonych i złotych na pomarańczowo-czerwono-niebieskie.
W 1986 drużyna zakupiła lub pozyskała z draftu Brada Daugherty, Marka Price, Rona Harpera i Larry'ego Nance. Tych czterech zawodników (dopóki Harper nie został sprzedany do Los Angeles Clippers w 1989 w zamian za prawa do Danny'ego Ferry) utworzyło trzon drużyny. Pod wodzą trenera Lenny'ego WilkensaCleveland osiągnęło play-off osiem razy w ciągu dziewięciu sezonów, w tym w ciągu trzech sezonów udało im się uzyskać ponad 50 zwycięstw.
W 1989 Cavs trafili w pierwszej rundzie play-off na Chicago Bulls. W czwartym meczu z serii do trzech zwycięstw Cleveland pokonali Chicago po dogrywce 108–105 i wyrównali serię na 2–2. Ostatni mecz był rozgrywany w Cleveland. Trzy sekundy przed końcem spotkania Cavaliers prowadziło jednym punktem. W ostatniej akcji piłkę otrzymał Michael Jordan, który trafił do kosza, mimo że próbował go powstrzymać Craig Ehlo. Ten fantastyczny rzut przeszedł do historii jako "The Shot". Największym osiągnięciem w tym okresie był sezon 1991-92, kiedy to w osiągnęli wynik 57–25 i awansowali do finału konferencji gdzie przegrali z Chicago Bulls 4–2.
Kiedy kariery zakończyli Nance, Daugherty i Price, drużyna nie była w stanie dobrze pokazać się w play-off. Po sezonie 1992-93, kiedy Cavaliers uzyskali wynik 54-28 w sezonie zasadniczym lecz przegrali we wczesnej fazie play-off, ówczesny trener Wilkens przeszedł do Atlanta Hawks.
W sezonie 1993-94 trenerem drużyny został Mike Fratello. Pod jego wodzą Cavaliers zostało jedną z najlepszych broniących drużyn w NBA, a ich głównym zawodnikiem był rozgrywający Terrell Brandon. Chociaż Cavs regularnie awansowali do play-off to nie udawało im się przejść pierwszej rundy.
W 1994 Cavs przenieśli się do Gund Arena, która mogła pomieścić 20 562 kibiców. Arena ta była także miejscem rozgrywania meczu gwiazd w 1997.
Niestety, nawet tacy zawodnicy jak Shawn Kemp i Žydrūnas Ilgauskas nie zapewnili drużynie sukcesów. Fratello został zwolniony w czasie sezonu 1998-99.
James był uznawany za gracza, który w przyszłości wniesie wiele dobrego do gry swojej drużyny. Sezon 2003-04zapowiadał się bardzo dobrze dla Cavaliers, a James zdobył miano najlepszego pierwszoroczniaka w NBA.Po sezonie 2002-2003 w Drafcie miał wziąć udział gwiazdor uczelni St. Vincent – St. Mary z Akron, znajdującego się zaledwie niecałe pięćdziesiąt kilometrów od Cleveland, LeBron James ogłoszony przez media na gracza pokroju Michaela Jordana i przyszłą wielką gwiazdę całej ligi. W środowisku NBA powszechny był pogląd, że słabo radząca sobie na początku sezonu drużyna Cavaliers specjalnie odpuściła drugą cześć sezonu, aby mieć jak największe szanse w losowaniu do Draftu na pierwszy numer. Tak też się stało i pod koniec czerwca w Madison Square Garden bez wahania wybrali Jamesa. W 2003 drużyna zmieniła także kolory koszulek z pomarańczowo-czerwono-niebieskich z powrotem na czerwono-złote.
Nadzieje były jeszcze większe w sezonie 2004-05, kiedy to James stał się supergwiazdą ligi poprawiając swoje wyniki w zdobytych punktach, skuteczności, liczbie asyst i zbiorek. Pomimo straty Carlosa Boozera z powodu kontrowersyjnego zajścia, James stworzył trzon drużyny z Žydrūnasem Ilgauskasem i Drew Goddenem. Po obiecującym początku sezonu końcówka nie była tak udana i Cleveland nie awansowała do play-off, zajmując 8. miejsce razem z New Jersey Nets i przegrywając dodatkowy mecz. Wyniki te spowodowały zwolnienie trenera drużyny Paula Silasa i menadżera Johna Paxsona.
Okres po sezonie 2004-05 był dla Cavaliers czasem wielu zmian. Nowym właścicielem drużyny został Dan Gilbert, nowym trenerem Mike Brown, a nowym menadżerem został były zawodnik Danny Ferry. W sezonie 2005-06 Cavaliers awansowali do play-off po raz pierwszy od sezonu 1997-98. Po zwycięstwie w pierwszej rundzie z Washington Wizards, przegrywali już 2–0 z Detroit Pistons w drugiej rundzie, aby wygrać trzy kolejne spotkania i wyjść na prowadzenie w serii. Jednakże przegrali zacięty szósty mecz u siebie, a następnie ponieśli porażkę w siódmym, decydującym meczu 79–61. Cavaliers ustanowili dwa rekordy w tym meczu: najmniejsza liczba punktów zdobyta w meczu (61) i najmniejsza liczba punktów zdobyta w jednej połowie (23).
W 2007 Cavs kontynuowali pasmo sukcesów uzyskując wynik 50-32 i awansując do play-off z drugiego miejsca, co pozwalało im mieć przewagę swojego parkietu aż do finału konferencji. Cavaliers wygrali w pierwszej rundzie 4-0 i było to ich pierwsze zwycięstwo do zera w historii. W drugiej rundzie Cleveland zmierzyło się z New Jersey Nets, których pokonali 4-2. W ostatnim spotkaniu, wygranym 88-72, James zdobył 23 punkty, 8 zbiórek i 8 asyst.
Cavaliers zmierzyli się z Pistons po raz drugi z rzędu w play-off, tym razem w finale konferencji. Po przegraniu dwóch spotkań w Detroit, Cleveland znów wyszło na prowadzenie 3-2, tak samo jak w ubiegłym roku, ale tym razem Cavaliers wyeliminowali Pistons po sześciu spotkaniach i zostali dopiero trzecią drużyną, która w finale konferencji przegrywając 0-2 awansowała do finału NBA. W ostatnim spotkaniu debiutant Daniel Gibson zdobył najwięcej punktów w karierze, 31. Finał NBA był krótką przygodą, ponieważ przegrali gładko 4-0 z San Antonio Spurs.
W sezonie 2007/2008 drużyna Cleveland Cavaliers dotarła do półfinału konferencji wschodniej, gdzie uległa zespołowi Boston Celtics, ale dopiero po siódmym spotkaniu w Bostonie, w którym świetnie zaprezentował się LeBron James, zdobywając 45 punktów. Jednak nie pozwoliło to drużynie ze stanu Ohio przechylić szali na swoja stronę. Wynik siódmego spotkania – 92-97.
W sezonie 2008/2009 "Kawalerzyści" osiągnęli najlepszy wynik w sezonie zasadniczym w całej NBA. Wynik 66- 16 był też najlepszym wynikiem w historii klubu z Ohio. Drużyna prowadzona przez LeBrona Jamesa była głównym faworytem do mistrzostwa. W pierwszej rundzie play-off "Kawalerzystom" przyszło się zmierzyć z Detroit Pistons. Ci jednak nie sprawili im trudności i Cleveland wygrali całą rywalizacje 4-0. W drugiej rundzie na Cavaliers czekała mocniejsza drużyna- Atlanta Hawks. Z nimi zawodnicy z Cleveland tez nie mieli problemów i wygrali 4-0. W finale konferencji przyszło im się zmierzyć z Orlando Magic. Cleveland niespodziewanie przegrali to rywalizacje 2-4 i pożegnali się z marzeniami o tytule.
8 lipca 2010 LeBron James podjął decyzję stworzenia tercetu z Dwyane'em Wade'em oraz Chrisem Boshem w Miami Heat.
W czasie przerwy między rozgrywkami w 2010 r. Cavaliers zwolnili trenera Mike'a Browna, razem z większością sztabu szkoleniowego. Menedżer Danny Ferryzrezygnował 4 czerwca 2010. Jego asystent Chris Grant awansował na jego miejsce. 1 lipca Cavaliers zatrudnili byłego rozgrywającego Los Angeles Lakers czy New Jersey Nets – Byrona Scotta, który w przeszłości trenował New Orleans Hornets. Jest to 18 trener w historii Cleveland Cavaliers.
Cavaliers spędzili resztę przerwy na odbudowywanie drużyny po odejściu Jamesa. 23 lipca podpisali kontrakt z ich 29 wyborem 2009 NBA Draft Christianem Eyenga. 26 lipca wymienili Delonte Westa i Sebastiana Telfaira do Minnesota Timberwolves za Ramona Sessionsa, Ryana Hollinsa oraz wybór w drugiej rundzie 2013 NBA Draft. 30 lipca zatrudnili Joeya Grahama, na rok za minimalną płacę dla weterana z opcją przedłużenia na rozgrywki 2011-12. 16 sierpnia Cavs zatrudnili niewybranego w 2010 NBA Draft, pierwszoroczniaka z Jamajki Samardo Samuelsa na 3 lata, kontraktem na 2,3 milionów dolarów. 20 września Jawad Williams oraz Cavs zdecydowali o podpisaniu nowej umowy na rok za 1,02 miliona dolarów. Po zakończeniu sezonu przygotowawczego 2010-2011 z rekordem 6-2 Cavs zdecydowali zwolnić Danny'ego Greena i zatrudnić niewybranego w drafcie Manny'ego Harrisa, przedłużono też kontrakt z J.J. Hicksonem na cztery kolejne lata. 18 listopada Cavaliers wysłali Christiana Eyenge do Erie BayHawks w NBA D-League. 27 grudnia zwolniono Jawada Williamsa oraz wysłano Samardo Samuelsa do NBA D-League. Dzień później zatrudniono Alonzo Gee. 1 i 2 stycznia 2011 przywrócono Samardo Samuelsa i Christiana Eyengę, z Erie BayHawks. 11 stycznia Cavaliers zostali rozgromieni przez Los Angeles Lakers aż 112-57. Była to jedna z najdotkliwszych porażek w historii organizacji. 24 lutego dokonano dwóch wymian podczas ostatniego dnia okienka transferowego. Cavaliers pozyskali byłego All-Stara Barona Davisa oraz wybór w pierwszej rundzie 2011 NBA Draft od Los Angeles Clippersw zamian za Mo Williamsa oraz Jamario Moona. Dokonano też wymiany z Boston Celtics, wybór w drugiej rundzie 2013 NBA Draft za Luke'a Harangody'ego i Semiha Erdena. Leon Powe został zwolniony aby zrobić miejsce w składzie dla nowego gracza.
Sezon 2010-2011 był kontrastem do tych z lat poprzednich. Cavaliers byli najgorsi w konferencji wschodniej z rekordem 19-63. Zanotowali również passę 26 porażek z rzędu, co jest niechlubnym rekordem w historii NBA. Wyrównali również rekord Tampa Bay Buccaneers z sezonu 1976-1977, który dotyczy najdłuższej serii porażek z rzędu w historii amerykańskiego profesjonalnego sportu.
Mający drugi najgorszy rekord w sezonie, Cavaliers mieli wysokie szanse na wylosowanie pierwszego wyboru w NBA Draft Lottery. Razem z 14-letnim synem właściciela Cavs, Nickiem Gilbertem, Cavs wylosowali dwa bardzo wysokie wybory 1 i 4. Co ciekawe, pierwszym wyborem okazał się ten który został oddany przez Clippers podczas wymiany w lutym, pomimo że miał tylko 2,8% szans na to że to będzie wybór 1. Cavaliers zostali pierwszą drużyną od sezonu 1983-1984, kiedyHouston Rockets mieli dwa wybory w pierwszej piątce draftu. W czasie draftu zostali wybrani Kyrie Irving z numerem 1, który był uważany za największą gwiazdę tego draftu, oraz niespodziewanie Kanadyjczyk Tristan Thompson z numerem 4, z uczelni Texas. Ponadto wybrano z numerem 32 Justina Harpera, który został jednak oddany do Orlando Magic za prawa do wyborów w drugich rundach draftów 2013 oraz 2014. Z numerem 54 wybrany został serb Milan Mačvan.