Upon Johnny Carson's retirement from The Tonight Show in 1992, executives at NBC announced Carson's frequent guest-host Jay Leno would be Carson's replacement, and not David Letterman. NBC later said that Letterman's high ratings for Late Night was the reason they kept him where he was. Letterman was reportedly bitterly disappointed and angry at not having been given The Tonight Show job; and at Carson's advice, Letterman left NBC after eleven years on Late Night. CBS signed Letterman to host his own show opposite The Tonight Show. He moved his show over to CBS virtually unchanged, taking most of the staff, skits, and comedy formats with him. However, NBC owned the rights to the Late Night name, forcing Letterman to re-christen his show Late Show with David Letterman. NBC was faced with an unexpected need to replace not just Letterman, but Late Night itself. They still owned the name, but needed to essentially build a new show from scratch. The show was first offered to Dana Carvey and Garry Shandling, who both turned it down. Saturday Night Live producer Lorne Michaels was brought in to develop the new show and auditions were held for the host. Comedians Jon Stewart, Drew Carey, and Paul Provenza auditioned. Michaels had suggested to O'Brien, a then-unknown comedy writer for The Simpsons and former writer for Saturday Night Live, that he should audition for the job, which he did on April 13, 1993. His guests were Jason Alexander and Mimi Rogers, and the audition took place on the set of "The Tonight Show." O'Brien was offered the show on April 26, 1993.

O'Brien's Late Night was rushed into production and debuted on September 13, 1993, with Andy Richter as O'Brien's sidekick. The premiere episode featured John Goodman (who received a "First Guest" medal for his appearance), Drew Barrymore, and Tony Randall. The episode featured a cold open of O'Brien's walk to the studio with constant reminders that he was expected to live up to Letterman, parodying a popular sentiment expressed in the media at the time. After seeming to be unaffected by the comments, O'Brien arrives at his dressing room and cheerfully prepares to hang himself. However, a warning that the show is about to start causes him to abandon his plans. The first musical guest on the show was the band Radiohead. The crowd for the first show mainly consisted of family members of the crew of the show so as to ensure a positive reception.

O'Brien's on-camera inexperience showed and the show's first fourteen weeks were generally considered mediocre. O'Brien, an unknown, was constantly at risk of being fired: NBC had him renewing short-term contracts, thirteen weeks at a time. He was reportedly on the brink of being fired at least once in this period, but NBC had no one to replace him. The show, and O'Brien, slowly improved through experience, and the show's ratings gradually increased to a level which allowed O'Brien to secure a longer contract, and not have to worry about cancellation.

In 2000, Richter left Late Night to pursue his acting career. The show's comedy bits and banter had usually depended on O'Brien's interaction with Richter. O'Brien's wacky non sequitur comedy became more pronounced as he played all of his comedy and commentary directly to the audience instead of towards Richter.

Ratings and reviews continued to improve for Late Night and in 2002, when time came to renew his contract, O'Brien had notable offers from other networks to defect. O'Brien decided to re-sign with NBC, however, joking that he initially wanted to make a 13-week deal (a nod to his first contract). He ultimately signed through 2005, indicating that it was symbolic of surpassing Letterman's run with 12 years of hosting.

• Official NBC Site: Late Night With Conan O'Brien