"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 Today"s 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 '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 record. It may be a conscious or an unconscious homage." Madonna denied any such influence, claiming that she had never heard of Love.