Wassim Zartek were the assistant recording engineers. According to the sheet music published by Musicnotes.com, "Beautiful Stranger" is set in common time and is composed in a key of F major with a mid dance tempo of 128 beats per minute. The song begins with a basic sequence of E–B–F–A–C before moving to the main chord progression of Csus4–C7. "Beautiful Stranger" is a psychedelic pop and disco song and begins with a musical instrumentation reminiscent of "Light My Fire" (1967) by The Doors and "Lucy in the Sky with Diamonds" (1967) by The Beatles. The song's main structure is backed by guitar, while drums come in during the choruses. Around the 1:06 mark, there is a hint of mellotron and flute being played like The Beatles' 1967 songs "Strawberry Fields Forever" or "The Fool on the Hill". The song has similar composition to Madonna's endeavors with her previous album Ray of Light, mixed with psychedelic music. USA Todays Ken Barnes has suggested that the chorus, riff, instrumentation and structure of "Beautiful Stranger" were based on American rock band Love's 1966 single "She Comes in Colors". The band's record company—Rhino Records—executive Gary Stewart stated that "Certainly, the riff and instrumentation [of 'Beautiful Stranger'] are reminiscent of 'She Comes in Colors,'" and that the "da da da da da" chorus on the track seems to be based upon "an instrumental flourish that's an integral part of the [Love] record. It may be a conscious or an unconscious homage." Madonna denied any such influence, claiming that she had never heard of Love. According to Michael Paoletta from Billboard, "no fierce-ruling club DJ in 1999 would [have] dared play the original jangly rock-etched version of the song". Hence the song was remixed by Victor Calderone, who kept the basic structure of the song, while mixing it with tribal infused beats. Unlike many of his then releases—where he removed the bulk of the song's lyrics for remixing—with "Beautiful Stranger" he kept them. Paoletta described the remixes as "if Calderone fully understands the importance of a song and understands how best to unite deft beats and a dazzling vocal performance." The remixes include a rock-leaning version as well as Calderone's Club and Radio mixes. Critical reception "Beautiful Stranger" received generally positive reviews. Chuck Taylor from Billboard denoted the song as a "new shift in the wind for [Madonna]", calling it another creative high for her. He