He served time in Attica prison during the early 1960s, where he embraced doctrines as diverse as Black Muslimism, Black Nationalism, Internationalism, and finally anarchism. In 1966 Sostre opened the Afro-Asian Bookstore in the black ghetto of Buffalo, New York. He is still alive and living in Manhattan with his wife Lizabeth Sostre and his sons Mark and Vincent Sostre.
For its somewhat short existence, Sostre's bookstore was a center for radical thought and education in the Buffalo ghetto. As Sostre details:
Arrested on July 14, 1967, at his bookstore, for "narcotics, riot, arson, and assault" (charges later proven to be fabricated, part and parcel of a COINTELPRO program in full swing), and convicted and sentenced to serve forty-one years and thirty days, Sostre became a jail house lawyer and regularly acted as legal council to other inmates, including winning two landmark legal cases involving prisoner rights: Sostre v. Rockefeller and Sostre v. Otis. According to Sostre, these decisions constituted "a resounding defeat for the establishment who will now find it exceedingly difficult to torture with impunity the thousands of captive black (and white) political prisoners illegally held in their concentration camps."
In earlier legal activity, Sostre secured religious rights for Black Muslim prisoners and also eliminated (in the words of Federal Judge Constance Motley) some of the more "outrageously inhuman aspects of solitary confinement in some of the state prisons.".
Lorenzo Kom'boa Ervin attributes his initial interest in anarchism to Sostre.
In 1974 Pacific Street Films debuted a documentary film on Sostre called Frame-up! The Imprisonment of Martin Sostre. It detailed Sostre's case with extensive interviews from prison.