Extraordinary Machine is the third studio album by American singer-songwriter Fiona Apple, released by Epic Records in the United States on October 4, 2005. Produced by Jon Brion, it was expected to be released in 2003 but was delayed several times by the record label without explanation, leading to speculation that a dispute had arisen over its commercial appeal. The controversy surrounding the album and leaked recordings of the Jon Brion sessions were the subject of substantial press attention, as well as a highly publicized fan-led campaign to see the album officially released. In collaboration with producers Mike Elizondo and Brian Kehew, Apple re-recorded the album over 2004 and 2005, and it was eventually released more than three years after the original recording sessions began.

The album was nominated for the Grammy Award for Best Pop Vocal Album in 2006. In 2009, Extraordinary Machine was named the 49th best album of the 2000s by Rolling Stone, and in 2020 was ranked at number 444 on the magazine's list of the 500 greatest albums of all time.

After completing a concert tour in support of her second album When the Pawn... (1999) in 2000, Fiona Apple relocated to Los Angeles. "The first couple of years [after Pawn], I didn't have anything left in me to write about ... I just figured if the songs came to me, they came to me, and if not, 'Oh, well, it's been fun'", she said. During her hiatus, Apple contemplated retiring from her recording career. In spring 2002 Apple and Jon Brion, her longtime friend and producer on When the Pawn, met for their weekly lunch meeting. Brion's five-year relationship with comedian Mary Lynn Rajskub had abruptly ended during the shooting of the Paul Thomas Anderson film Punch-Drunk Love (2002), which Brion was scoring. He reportedly "begged" Apple to make another album after being forced to watch hours of footage of Rajskub while working on the film: "I need work that can save me". Apple agreed, and Brion went to Apple's label, Epic Records, with strict stipulations (including no deadline), to which the label eventually agreed. A tentative November 2002 release date was then set.

After performing the then-untitled "Not About Love" at a Brion concert in February, Apple started studio work on the album the following June at Ocean Way Recording, where she played for Brion the first five songs she had written for the album. She debuted the song "A New Version of Me" (later renamed "Better", and then "Better Version of Me") live at Club Largo—where Brion has a regular Friday-night gig, often joined by musical friends—in August. By late 2002, Apple, Brion, engineer Tom Biller and percussionist Matt Chamberlain were at work in a wing of the Paramour Mansion, which was built in 1923 by silent film star Antonio Moreno; the four used the building as a temporary residence from early 2003, and Chamberlain said the experience of recording there was "completely amazing". With the album half complete in April 2003, Brion, Apple and Biller worked at Cello Studios, and a new release date of July 22 was announced. Brion and Apple then travelled to England later that month, to record strings and orchestration for the songs at Abbey Road Studios in London. The album was completed from Brion's perspective by May 2003, at which point the release was pushed back to September 30. But by fall 2003, Apple and Brion were back in the recording studio adding finishing touches to the album, thus forcing back the release date to February 2004 (this was later changed to "early 2004").

Little by little, small details about the songs were revealed through newspaper and magazine articles. An August 2003 article on Jon Brion in The New York Times revealed the title of another song on the album, "Oh Well", with Brion stating that he cried the first time he heard Apple play it. Brion worked solidly on "Oh Well" for over a week, and would later refer to it as the album's "problem child". The November 13, 2003 issue of Rolling Stone reported that the album was "definitely eclectic" and quoted Apple admitting that the album was "all over the place". The slow-paced track "Extraordinary" was referred to as "a Tin Pan Alley-esque blend of Tom Waits and Vaudeville", while the much more energetic "Better" was described as "an OutKast-like deluge of beats". In February 2004, an item in Spin magazine confirmed the title of the album and a new song, "Red, Red, Red", which Apple said was inspired by a book about optical illusions.

In late June 2004, the song "Extraordinary"—which had since been retitled as the title track—was leaked onto the internet. Soon after, a "rough mix" of "Better Version of Me" also leaked, with the following inscription listed as a comment in the properties of the MP3 file: "It has some good bits, but I still think we never have topped the second version. Ideally, we would combine some of this with that, but obviously we can't. Sigh. Ask the others what they think—I know she was partial to both of them, particularly the second". Josh Korr of the Tampa Bay Times wrote, "With a playfulness and penchant for odd sounds and instruments that channel the spirit of Brian Wilson's Smile, Apple's first songs since 1999 make Norah Jones, Joss Stone, Alicia Keys and other pretenders sound like American Idol rejects", while Entertainment Weekly called the songs "tantalizing, brazenly eccentric art pop ... With Apple, the weirder, the better".

After months of no official news, an article about Jon Brion appeared in an October 2004 issue of Entertainment Weekly. In it Brion is reported to have said that the album had been shelved since its completion in May 2003 due to the label not hearing any obvious singles. A representative for Epic Records stated that the album was to be released in February 2005, and that Apple had decided to re-record some of the songs. Brion later clarified the status of the album in an interview with MTV News in January 2005, stating that Epic had desired material in the vein of Apple's debut album Tidal (1996), but that when confronted by Machine, "it's just not the obvious easy sell to them". When USA Today asked Apple herself about when the album would be released, she replied, "You'll probably know before I do".

Shortly thereafter, Fiona Apple fans organized a week-long mail campaign to flood Sony with support for Apple and for the release of the album. In response to the campaign, Epic president Steve Barnett said, "It's our understanding that Fiona is still in the midst of recording her next album, and we at Epic Records join music lovers everywhere in eagerly anticipating her next release". On February 26, 2005, radio DJ Andrew Harms at 107.7 The End in Seattle began playing previously unheard tracks from a bootleg copy of the album, and before long, poor quality copies of "Not About Love", "Get Him Back" and "Used to Love Him" were circulating on the internet. Harms said of the situation, "this is pretty special [...] with an established [artist] like Fiona, to have that happen is pretty crazy, so to stumble upon a full-length copy of the record was incredible", also noting the positive response from listeners the songs had received.