Lenny Bruce was born Leonard Alfred Schneider to a Jewish family in Mineola, New York, grew up in nearby Bellmore, and attended Wellington C. Mepham High School. Lenny's parents divorced before he turned 10, and he lived with various relatives over the next decade. His British-born father, Myron (Mickey) Schneider, was a shoe clerk, and the two saw each other very infrequently. Bruce's mother, Sally Marr (legal name Sadie Schneider, born Sadie Kitchenberg), was a stage performer and had an enormous influence on Bruce's career.
After spending time working on a farm, Bruce joined the United States Navy at the age of 16 in 1942, and saw active duty during World War II aboard the USS Brooklyn (CL-40) fighting in Northern Africa; Palermo, Italy, in 1943; and Anzio, Italy, in 1944. In May 1945, after a comedic performance for his shipmates in which he was dressed in drag, his commanding officers became upset. He defiantly convinced his ship's medical officer that he was experiencing homosexual urges. This led to his undesirable discharge in July 1945. However, he had not admitted to or been found guilty of any breach of naval regulations and successfully applied to have his discharge changed to "Under Honorable Conditions ... by reason of unsuitability for the naval service". In 1959, while taping the first episode of Hugh Hefner's Playboy's Penthouse, Bruce talked about his Navy experience and showed a tattoo he received in Malta in 1942.
After a short stint in California spent living with his father, Bruce settled in New York City, hoping to establish himself as a comedian. However, he found it difficult to differentiate himself from the thousands of other show business hopefuls who populated the city. One locale where they congregated was Hanson's, the diner where Bruce first met the comedian Joe Ancis, who had a profound influence on Bruce's approach to comedy. Many of Bruce's later routines reflected his meticulous schooling at the hands of Ancis. According to Bruce's biographer Albert Goldman, Ancis's humor involved stream-of-consciousness sexual fantasies and references to jazz.
Bruce took the stage as "Lenny Marsalle" one evening at the Victory Club, as a stand-in master of ceremonies for one of his mother's shows. His ad-libs earned him some laughs. Soon afterward, in 1947, just after changing his last name to Bruce, he earned $12 and a free spaghetti dinner for his first stand-up performance in Brooklyn. He was later a guest—and was introduced by his mother, who called herself "Sally Bruce"—on the Arthur Godfrey's Talent Scouts radio program. Lenny did a bit inspired by Sid Caesar, "The Bavarian Mimic", featuring impressions of American movie stars (e.g., Humphrey Bogart, James Cagney, and Edward G. Robinson).