Polyacrylamide gel electrophoresis (PAGE) is a powerful technique for separating proteins extracted from complex biological samples. Unfortunately, the difficulty of recovering intact proteins in high yield from polyacrylamide matrices often limits further analyses. We discovered that staining proteins with Coomassie brilliant blue (CBB) immediately after electrophoresis improves extraction efficiency. Post-staining, proteins widely varying in molecular weight were recovered at high efficiency with a 10 minute procedure that did not employ a surfactant. High recoveries were also obtained from dried, archived gels. Native-PAGE separated protein complexes larger than 400 kDa were recovered in an alternative procedure that substituted the mild detergent octyl-β-D glucopyranoside for CBB. Recovered proteins retained their native structure and were amenable to structural analysis by native mass spectrometry. The established workflows facilitate in-depth proteomic and protein structure analyses as well as the purification, storage, and transport of protein samples.