Kariera z Ozzym Osbourne'em W 1979, frontman zespołu Black Sabbath – Ozzy Osbourne, zdecydował się na stworzenie nowego zespołu. Basista Dan Strum zarekomendował Ozzy'emu właśnie Randy'ego. Rhoads dostał telefon z propozycją przesłuchania tuż przed jego ostatnim występem z zespołem Quiet Riot. Na przesłuchanie przyszedł z własną gitarą (Gibson Les Paul), wzmacniaczem i zaczął grać; gdy Osbourne usłyszał, co potrafi Rhoads, natychmiast dał mu pracę. Rhoads wspominał później, „Po prostu nastroiłem gitarę, zagrałem kilka riffów, a on powiedział: masz występ. Dziwnie się czułem. Przecież nigdy wcześniej mnie nie słyszałeś – pomyślałem”. Osbourne określił grę Rhoadsa jako „Bóg wchodzi w moje życie”.
W marcu 1980 roku zespół Osbourne'a przybył do Anglii, aby zacząć pracę nad swoim pierwszym albumem – Blizzard of Ozz. W grze Rhoadsa widoczny był postęp w stosunku do występów w Quiet Riot – coraz odważniej wprowadzał do swoich partii elementy gry neoklasycznej. Fani rocka (szczególnie w USA) przyjęli styl Rhoadsa bardzo pozytywnie. Album promowały dwa single: Goodbye to Romance oraz Crazy Train.