(FORTUNE Small Business) – It's tough to think of many places where the word "playboy" doesn't instantly evoke images of cleavage and mirrored ceilings. But even Hugh Hefner had to get his foot--or another body part--in the door at the start. When we asked celebrated entrepreneurs how they did it, we heard tales in the great American sales traditions of relentless optimism, persistence, and door-to-door legwork. But it's all in the details....

Direct mail: Hefner's Playboy magazine--then called Stag Party--was a radical concept in buttoned-down 1953--not a girlie mag, but not an "art" nude book either. This was a good-life guide for Hefner's peer group, guys he felt had "missed out on the party'' during World War II and the domestic hunker-down that followed. Hefner sent letters to hundreds of men--guys he knew from the magazine-distribution business--promising not only a no-sale-no-fee deal, but also a "full-color, full-page, male-pleasing nude study" of Marilyn Monroe. He signed using different titles for himself (president, editor), depending on the recipient. Even then, it took the first issue's appearance to really arouse people....

Only K'NEX: Hanging on Joel Glickman's wall are those classic success-story mementos: nicely framed rejection letters from the big guys. Glickman had tried to sell Mattel and Hasbro his new construction toy, K'NEX, but they weren't interested. So Glickman took a route that's also a classic: personal connections. Working the grapevine, Glickman turned up a friend who had a friend who had a friend, and snagged a meeting with a Toys "R" Us buyer. Six weeks after his K'NEX hit the shelves, the toy had racked up $1.5 million in sales. Those early rejection letters, Glickman says, didn't exactly deter him. "If [the manufacturers] were that dumb," he figured, "what they knew couldn't be that hard to learn."...

Hands on: In 1980, John Paul DeJoria, a former VP for a hair-products company, was living out of his car. Granted, it was a 1960 Silver Cloud Rolls, but going from door to door was no smooth ride. DeJoria or his partner, Paul Mitchell (now deceased), would corner a stylist, hold out a hand containing a dime-sized dab of their shampoo ("like a gem," DeJoria recalls), and ask them to feel how rich it was. A little dab--and one sudsing--would do you, saving money and time. Half the salons turned them down. The other half gave Paul Mitchell products their start....

The roar of the media: Bobbi Brown got her foot in the door long before she tried selling her cosmetics line. Arriving in New York City in 1980 straight from college, she knocked on the doors of small magazines, getting gigs doing makeup for their photo shoots. By 1989 she had clients like Vogue, and an editor at Glamour ran an item about Brown's own lipstick. Brown has all the smarts you'd expect. She also knows the power of free publicity: "A reason I was in business at all was because I got so much press."...

Bellying up to the bar: In 1985, after all the distributors in Boston turned him down, Jim Koch rented a truck, filled his briefcase with cooler packs and beer bottles, and went from bar to bar. He urged every bartender to take a sip of his Samuel Adams Boston Lager and told them how his grandfather had come up with the recipe. He scored big on his first visit to the legendary Doyle's pub, then clinched his rep with a first-place prize at a national brewers' contest. Koch's own recipe: "When you can't get in the front door, use the back; when you can't get in there, use the window."

--LOUISE ROSEN