Das Plattenlabel Prestige Records wurde von Bob Weinstock 1949 zunächst unter dem Namen New Jazz gegründet, aber schon ein Jahr später in Prestige umbenannt. Weinstock, der am 14. Januar 2006 im Alter von 77 Jahren verstarb, war dafür bekannt, daß er seine Künstler - darunter solche Größen wie Miles Davis, John Coltrane, Sonny Rollins, Thelonious Monk, Sonny Stitt, Eric Dolphy, Mose Allison, Red Garland und Gene Ammons - dazu ermutigte, ohne vorherige Proben ins Aufnahmestudio zu gehen, um die Einspielungen so authentisch und aufregend wie nur möglich klingen zu lassen.
Zur Seite stand ihm dabei in den 50er und 60er Jahren vor allem der Toningenieur Rudy Van Gelder und in den frühen 50ern als gelegentlicher Produzent auch der bekannte Jazzkritiker Ira Gitler. 1958 begann Prestige Records sein musikalisches Programm zu diversifizieren und erweckte das einstige Label New Jazz zu neuem Leben, um darauf Alben von talentierten Newcomern herauszubringen. Mit Swingsville und Moodsville wurden noch zwei Sublabels geschaffen, die aber nur kurze Zeit aktiv waren. Die darauf erschienen Aufnahmen wurden in den 60ern auf Prestige Records selbst wiederveröffentlicht. Ein weiteres, langlebigeres Sublabel trug den Namen Bluesville.
In den 60er Jahren zog sich Weinstock von der Produktionsarbeit zurück und überließ diese Chris Albertson, Ozzie Cadena, Esmond Edwards, Don Schlitten und andere Produzenten. Zu den Musiker, die damals bei Prestige Reords unter Vertrag waren, gehörten unter anderem der Pianist Jaki Byard und der Tenorsaxophonist Booker Ervin. Obwohl der künstlerische Standard nach wie vor hoch war, konnte das Prestige-Label mit seinen neuen Einspielungen nicht an die Erfolge anschließen, die es einst mit den legendären Alben von Miles, Coltrane und Monk genossen hatte. Kommerziell erfolgreiche Soul-Jazz-Künstler wie Charles Earland, Richard "Groove" Holmes und Brother Jack McDuff sicherten dem Label aber das Überleben.
1971 wurde Prestige Records von Fantasy Records aufgekauft. Die Alben, die in den 50er und 60er Jahren Jazzgeschichte gemacht hatten, wurden auf CD in der bekannten Reihe "Original Jazz Classics" wiederveröffentlicht.