The group began work on Red Medicine in 1994, after touring in support of In on the Kill Taker. The writing of the album consisted of several months of jam sessions and recording at Guilford House, a secluded country estate located in Guilford, Connecticut.
The album's recording sessions took place from January to February 1995 at Inner Ear Studios in Arlington, VA. The band worked with engineer Don Zientara, but did not choose to work with producer Ted Niceley again. Fugazi opted to retreat from the in-your-face production values of In on the Kill Taker and instead worked to create an ambient sound which would display greater depth. To achieve this, the band handled production duties themselves, and in doing so, became more confident with in-studio experimentation. This is evident in the incorporation of short, sampled segues, ("Do You Like Me", "Birthday Pony"), instruments such as clarinet, (as heard on "Version"), and alternate tunings used on songs such as "Latest Disgrace" and "By You". Footage of the band both writing and recording the album can be seen in the film Instrument.
The album entered the Billboard 200 charts and sold over 160,000 copies in its first week of release. It was also a critical success: Steve Huey of AllMusic gave the album 4 1/2 out of 5 stars and stated, "With more drive and playful goings-on, the arrangements sound much looser than on Kill Taker, while remaining just as gut-kicking and brainy." Mark Kemp of Rolling Stone gave the album 4 stars and called Red Medicine "rock solid."Pitchfork put the album at number 42 in its Top 100 Albums of the 90s.