Fugazi began writing the material for Red Medicine in late 1994, after touring in support of In on the Kill Taker.
Nhóm bắt đầu viết Red Medicine vào cuối 1994, sau khi tour quảng bá In on the Kill Taker.