Complex sentence: They began in 1978 with the release of "Classic Rock" on K-Tel Records.
Split into simpler sentences: They began in 1978 with the release of "Classic Rock". It was released on K-Tel Records.