On June 11, 1836, New York City stone mason Robert Haslem went looking for a little nocturnal fun. He found it on Bleecker Street in the form of a pretty black prostitute, who took him to an alley near her house at 108 Greene St. (between Prince and Spring Sts.), a known whorehouse, where they got down to business. Afterward they parted ways, only for Haslem to realize that his wallet was missing. He reported the theft to police, who wasted no time in going undercover to catch the pilfering hooker, and she was promptly nabbed. Or rather, he was promptly nabbed. Though the prostitute initially gave her name as Mary Jones, police realized during a strip search that this was not genetically your average Mary. The detainee owned up to actually being Peter Sewally, cook and waiter by day, lady of the evening by night.
The local press of the era had a field day with the case. When it was revealed that Sewally had actually fashioned a makeshift vagina out of cow skin that he wore tied around his waist to fool (and presumably please) his customers, he was dubbed Beefsteak Pete. The New York Sun reported that under the alternate monikers Miss Ophelia, Miss June, and Eliza Smith, Sewally "at night prowls about the five points (of Gangs of New York fame, near the modern corner of Baxter and Worth Sts.) and other similar parts of the city, in the disguise of a female, for the purpose of enticing men into the dens of prostitution, where he picks their pockets if practicable."
At his trial a week post-capture, Sewally, who said he was 32 years old and a New York City native, denied ever meeting Haslem, much less taking his or any other wallet. He also seemed surprised that anyone would be shocked by his cross-dressing. "I have always attended parties among the people of my own color dressed in this way—and in New Orleans I always dressed in this way," he said. He was found guilty of grand larceny and sentenced to five years in state prison, but reappeared in news accounts several times in the ensuing years, invariably for the same offense, to which he appears to have been quite committed despite the consequences. On May 16, 1853, the New York Times reported that at 3 a.m. the previous morning, Sewally was arrested just days after being released from yet another five-year sentence at Sing Sing. It's the last we know of his whereabouts.
For a more detailed account of Peter Sewally's life and notoriety, see OutHistory.org.