The album was originally due to have been issued in late 2000, with the track "Roll Out" being issued as a promotional single that fall. However, the album was later held over and reworked. Timbaland and Magoo's regular collaborators, including Playa and Mad Skillz, appear on the album. Indecent Proposal includes several tracks featuring Timbaland's latest collaborators, Petey Pablo and Sebastian, who is also Timbaland's brother. Sebastian was one of several artists signed to Timbaland's short-lived Beat Club Records, as was Ms. Jade, who appears on "In Time". The album also features high-profile guest appearances by Jay-Z, and Ludacris, the latter of which had worked with Timbaland prior to becoming famous. Certain instrumentals used on the album were originally intended for Ginuwine's third LP, Life, but his record label, 550 Music, went against Timbaland producing the whole album - so Timbaland took some of the instrumentals and used them for himself.
Although "Roll Out" was issued as a promotional single in September 2000, the two official singles from Indecent Proposal were "Drop", featuring Fatman Scoop, and the Indian-influenced "All Ya'll". The final track on the album, "I am Music", was recorded as a Da Bassment reunion collaboration between Aaliyah, Playa, and rock musician Beck. However, Timbaland did not include Beck's vocal on the final released master - the final version instead features Timbaland's original demo vocals, which appear in Beck's place. By the time the LP was released, Aaliyah had died in a plane crash, on August 25, 2001. The LP was dedicated to her memory.