Born in New York City, Weinstock began his career selling records, with a particular emphasis on the new bebop movement. In 1949, at the age of 20, he made his first recording, of the forward-looking pianist Lennie Tristano.

Among the best known releases from the label were four albums recorded by Davis, with Coltrane, pianist Red Garland, drummer Philly Joe Jones, and bassist Paul Chambers, in 1956: Cookin' With the Miles Davis Quintet, Relaxin', Workin', and Steamin'. According to the Times, the seminal recordings were made in two days, with no second takes, as the price for releasing Davis from his contract.

After selling Prestige, which is now part of the Concord Record Group, Weinstock moved to Florida.