The lead character is based on Washington, D.C. hostess and Democratic Party fundraiser Perle Mesta, who was appointed the Ambassador to Luxembourg in 1949. The Playbill distributed at each performance humorously noted that "neither the character of Mrs. Sally Adams nor Miss Ethel Merman resemble any person living or dead."
In 1949, Merman and her family were vacationing at the Hotel Colorado in Glenwood Springs with Howard Lindsay and his wife Dorothy Stickney. Watching Merman poolside while reading a magazine article about Mesta, Lindsay was struck by how typically "American" she was and immediately envisioned her portraying a colorful character similar to the newly appointed ambassador. When he proposed the idea to Merman, who had little interest in either society or political news, she responded, "Who's Perle Mesta?"
Although Merman had announced she was interested in playing a dramatic role in her next project, Lindsay and Russel Crouse approached Irving Berlin and began working on the book for Call Me Madam when he expressed interest in composing the score. Berlin's last production, Miss Liberty, had failed to recoup its investment, and he was determined to repeat the success he had had with Annie Get Your Gun. The three collaborators agreed they needed to treat their subject with care to avoid any legal action by Mesta. As the work progressed, Merman conceded she would be willing to sing two or three songs, but eventually accepted the fact she was going to star in a full-scale musical comedy instead of the drama she preferred.
Producer Leland Hayward budgeted the production at $250,000. In exchange for the original cast recording and television broadcast rights, he arranged to have it financed 100% by RCA Records and NBC, with the two sharing 35% of the net earnings. In order to increase the profits, Hayward decided to charge an all-time high of $7.20 for orchestra seats.
Hayward hired George Abbott to direct, and Abbott and casting director Harold Prince auditioned thousands of actors for the twenty speaking roles and twenty-nine chorus members. Raoul Pene du Bois was hired to design sets and costumes, although the wardrobe worn by Merman was the responsibility of Mainbocher.
Once the script was completed, everyone agreed that while it was little more than standard situation comedy material it was a perfect vehicle for Merman, and that Berlin's score, although far from his best, was tuneful and memorable. It included the comic song "Mr. Monotony", which originally was written for and dropped from the film Easter Parade. Berlin had then included it in Miss Liberty, but it was dropped from that as well. In this instance, the third time was not the charm; during out-of-town tryouts, Merman insisted it be dropped. (In 1989, Sarah Brightman recorded it for her CD The Songs That Got Away.) To fill the hole its omission left in the second act, Berlin wrote "Something to Dance About" to give the second act a lively opening. When the star requested a duet with Russell Nype playing her lovestruck press attache Berlin responded by writing the counterpoint tune "You're Just in Love" and it ultimately became a showstopper at every performance.
Directed by George Abbott and choreographed by Jerome Robbins, the musical premiered at the Shubert Theatre in New Haven, Connecticut on September 11, 1950. Reviews were mixed - Variety said it "inspires warm applause rather than cheer"—and Berlin wrote two new songs to bolster the sagging second act. It opened in Boston on September 19, and while The Boston Record thought it offered "only an occasional flash of inspirational fire", it played to standing-room-only audiences throughout the run.
With a record advance sale of $2 million, the Broadway production opened on October 12 at the Imperial Theatre, where it ran for 644 performances and grossed more than $4 million. In addition to Merman and Nype, the cast included Paul Lukas, Pat Harrington, Sr., Lilia Skala, and Richard Eastham. Brooks Atkinson of The New York Times thought it offered one of Berlin's "most enchanting scores: fresh, light, and beguiling, and fitted to lyrics that fall out of it with grace and humor", and the New York Post called Merman "indescribably soul-satisfying", "a comedienne of rare skill", and "one of the joys of the world." She remained with the show for the entire run and appeared in the limited four-week engagement staged to celebrate the reopening of the National Theatre in Washington, D.C., but her understudy Elaine Stritch starred in the national tour.
The musical opened in the West End at the London Coliseum on March 15, 1952 where it ran for 486 performances and starred Billie Worth.
The New York City Center Encores! semi-staged concert version starring Tyne Daly was presented in February 1995. A regional production ran at the Paper Mill Playhouse, Millburn, New Jersey, in April–May 1996 and starred Leslie Uggams.