The mission was the first to use the super lightweight external tank (SLWT) which was the same size, at 154 feet (47 m) long and 27 feet (8.2 m) in diameter, as the external tank used on previous launches, but 7,500 pounds (3,400 kg) lighter. The tank was made of an aluminium lithium alloy and the tank's structural design had also been improved making it 30 percent stronger and 5 percent less dense. The walls of the redesigned hydrogen tank were machined in an orthogonal waffle-like pattern, providing more strength and stability than the previous design. These improvements would later provide additional payload capacity to the International Space Station.
Docking of Discovery to Mir, the first for that orbiter, occurred at 16:01 UTC, 4 June 1998 at an altitude of 208 miles. Hatches opened at 2:34 pm the same day. At hatch opening, Andy Thomas officially became a member of Discovery's crew, completing 130 days of living and working on Mir. The transfer wrapped up a total of 907 days spent by seven U.S. astronauts aboard the Russian space station as long-duration crew members. During the next four days, the Mir 25 and STS-91 crews transferred more than 500 kilograms (1,100 lb) of water, and almost 2,130 kilograms (4,700 lb) of cargo experiments and supplies were exchanged between the two spacecraft. During this time, long-term U.S. experiments aboard the Mir were moved into Discovery's middeck locker area and the SPACEHAB single module in the orbiter's payload bay, including the Space Acceleration Measurement System (SAMS) and the tissue engineering co-culture (COCULT) investigations, as well as two crystal growth experiments. The crews also conducted Risk Mitigation Experiments (RMEs) and Human Life Sciences (HLS) investigations. When the hatches closed for undocking at 9:07 am, 8 June, and the spacecraft separated at 12:01 pm that day, the final Shuttle-Mir docking mission was concluded and Phase 1 of the International Space Station (ISS) program came to an end.

Mir as seen from Discovery after undocking
STS-91 also carried a prototype of the Alpha Magnetic Spectrometer (AMS) into space. The AMS, designed to look for dark and missing matter in the universe, was powered up on Flight Day 1. Data originally planned to be sent to ground stations through Discovery's Ku-band communications system was recorded on board because of a problem with the Ku-band system that prevented it from sending high-rate communications, including television signals, to the ground. The system was able to receive uplink transmissions. On 3 June 1998 the crew was able to set up a bypass system that allowed AMS data to be downlinked via S-band/FM communications when the orbiter came within range of a ground station. Data that could not be recorded by ground stations was recorded on board throughout the mission.

The Ku-band system failure was determined to be located in a component that was not accessible to the crew. The failure prevented television transmission throughout the mission. Television broadcasts from Mir were prevented by a problem between a Russian ground station and the mission control center outside Moscow, limiting communications to audio only on NASA television.

Other experiments conducted by the Shuttle crew during the mission included a checkout of the orbiter's robot arm to evaluate new electronics and software and the Orbiter Space Vision System for use during assembly missions for the ISS. Also on board in the payload bay were eight Get Away Special experiments, while combustion, crystal growth and radiation monitoring experiments were conducted in Discovery's mid-deck crew cabin area.