Start von Cape Canaveral (KSC) und Landung auf Cape Canaveral (KSC), Runway 15. Der Start war bereits für den 01. Juli 2006 vorgesehen, jedoch musste der Countdown wegen eines herannahenden Sommergewitters abgebrochen werden. Für den zweiten Startversuch am folgenden Tag sah die Wetterprognose noch schlechter aus, sodass die Astronauten die Raumfähre unverrichteter Dinge wieder verlassen mussten. Der Start wurde um zwei Tage auf den 04. Juli 2006 verschoben. Die 48-stündige Verschiebung war nötig, um die Tanks für flüssigen Sauerstoff und flüssigen Wasserstoff in der Nutzlastbucht des Shuttles wieder aufzufüllen. Damit werden die Brennstoffzellen betrieben, die die Bordelektrik versorgen.

Bei STS-121 handelt es sich um einen eingeschobenen Flug, der von der NASA im Jahr 2003 ins Programm genommen wurde. Es hatte sich herausgestellt, dass die von STS-114 nach der durch den Columbia-Absturz verursachten Zwangspause zu bewältigenden Aufgaben zu umfangreich für eine Mission sein würden. Für die NASA sind deshalb STS-114 und STS-121 miteinander verbunden. Sie sieht beide Missionen als Testflüge an, die die Wiederaufnahme der Shuttle-Flüge unter der Bezeichnung "Return to Flight" dokumentieren. Die ersten Planungen sahen einen Start im November 2004 vor, als die NASA-Leitung im Herbst 2003 davon ausging, STS-114 im September 2004 durchführen zu können. Mit der Verschiebung von STS-114 sollte sich auch der Beginn von STS-121 verzögern. Als die Discovery schließlich Ende Juli 2005 zur ISS aufbrach, sollte die Raumfähre Atlantis zwei Monate später folgen. Während des Starts von STS-114 lösten sich jedoch wieder Teile der Schaumstoffisolierung des Außentanks. Deshalb setzte die US-Raumfahrtbehörde, noch bevor die Discovery zur Erde zurückgekehrt war, alle weiteren Flüge aus. Zunächst sollte endlich geklärt werden, warum immer wieder Teile der Isolierung abplatzten, und dafür eine Lösung gefunden werden.

Zu den Hauptzielen der Mission ISS ULF-1.1 gehörten Tests neuer Reparaturtechniken als Folge des Unglücks der Columbia im Februar 2003 sowie die Auslieferung von Ausrüstungsgegenständen. Auf dem Weg zur ISS wurde das 15 Meter lange Orbiter Boom Sensor System (OBSS) mit zwei Laser-Systemen und einer hochauflösenden Videokamera benutzt, um die Unterseite des Space Shuttles auf Beschädigungen hin zu untersuchen.
Mit dem Flug wurde die Besatzung der ISS um ein Besatzungsmitglied aufgestockt. Damit arbeiteten erstmals seit der sechsten Expedition wieder drei Raumfahrer auf der Station. Der deutsche Astronaut Thomas Reiter verblieb noch das kommende halbe Jahr nach der Mission auf der ISS. Daneben gehörte der Transport von Gütern zu den Aufgaben von STS-121. Ein Großteil der über 4 Tonnen Fracht wurden mit dem Logistikmodul Leonardo (2,4 Tonnen) zur Station gebracht.

Das Multi-Purpose Logistics Module (MPLM) Leonardo, (Deutsch Mehrzwecklogistikmodul), wurde verwendet, um bei Space-Shuttle-Missionen Frachten zu und von der Internationalen Raumstation (ISS) in einem unter Luftdruck stehenden Raum zu transportieren.
Das Modul wurde während des Transportes mit dem Shuttle in dessen Ladebucht befestigt. Nach dem Andocken an die ISS wurde das MPLM mit Hilfe des Roboterarmes Canadarm2 aus der Ladebucht gehoben und am Unity-Modul angekoppelt. Anschließend wurde die Luke des Moduls geöffnet und die Astronauten erhielten Zugang zum MPLM, um es zu entladen sowie mit den zur Erde zu bringenden Frachten zu beladen. Bevor das Shuttle von der Station ablegte, wurde das Modul wieder in der Ladebucht befestigt und kehrte anschließend zusammen mit der Raumfähre zur Erde zurück.
Der wesentliche Vorteil dieses Verfahrens lag darin, dass Transportgüter, insbesondere die sogenannten International Standard Payload Racks, direkt vom MPLM in den amerikanischen Teil der Station verladen werden konnten. Kopplungsadapter vom APAS-Typ russischer Bauart, die auch zum Andocken des Space Shuttles benutzt werden, haben einen wesentlich geringeren Durchmesser und lassen kein Verladen sperriger Gegenstände zu. Weiterhin ermöglichte der Einsatz des MPLM, nicht mehr benötigte Ausrüstung und beendete Experimente zurück zur Erde zu transportieren. Andere Transportschiffe wie die unbemannten Progress- und ATV-Frachter verglühen beim Wiedereintritt und transportieren daher ausschließlich Müll von der Station ab.

Nach dem Erreichen der Erdumlaufbahn öffnete die Besatzung die Frachtraumtüren der Discovery, testete den Greifarm RMS in seinen verschiedensten Funktionen, klappte die für das Rendezvous erforderliche Ku-Band-Antenne aus und begann mit der Angleichung der Flugbahn zur Internationalen Raumstation. Ebenso montierten sie im "Orbiter Docking System" die "Centerline Camera", die Kommandant Steven Lindsey das spätere Docking erleichtern soll. Außerdem wurde der Hitzeschild der Discovery auf eventuelle Schäden untersucht, die beim Start durch sich vom Außentank ablösende Isolierschaumstücke entstanden sein könnten. Dabei wurde der OBSS-Inspektionsarm eingesetzt, der nach dem Columbia-Unglück entwickelt wurde. Der OBSS ist ein 15 Meter langer "Aufsatz", der mit dem Roboterarm des Shuttles verbunden wird. Der Kopf des OBSS ist mit Laser-Sensoren und hochauflösenden Kameras ausgestattet und tastet halbautomatisch die Hitzeschutzkacheln des Orbiters ab.

Den Gesetzen der Bahnmechanik folgend holte die Discovery von ihrer ersten Umlaufbahn und weiteren Triebwerkszündungen in den folgenden beiden Tagen immer mehr zur Internationalen Raumstation auf. Am dritten Flugtag, dem 06. Juli 2006, hatte die Discovery einen Punkt 15 Kilometer hinter der Raumstation erreicht. Für den Anflug im Rahmen des sogenannten "R-Bar Approach" musste das Space Shuttle nochmals seine Bahn senken, sodass sich die Discovery schließlich etwa 180 Meter unterhalb der Internationalen Raumstation befand. Ab dieser Distanz übernahm Steven Lindsey die manuelle Steuerung und flog entlang des sogenannten "R-Bar" (gedachte Verbindungslinie zwischen der Raumstation und dem Erdmittelpunkt) hinauf zur ISS. In der Nähe der Station führte Steven Lindsey ein spektakuläres 360°-Manöver - das Rendezvous Pitch Maneuver (RPM) - durch, wobei er die Raumfähre innerhalb weniger Minuten um ihre Querachse drehen ließ. Die Besatzung der Raumstation fertigte währenddessen hochauflösende Aufnahmen des Shuttle-Hitzeschildes an. Die Aufnahmen werden später zur Erde übertragen und von Fachleuten ausgewertet. Mit einer direkt vor der ISS reduzierten Annäherungsgeschwindigkeit auf zuletzt nur noch 3 Zentimeter pro Sekunde flog der Orbiter auf den Ankopplungsstutzen der Internationalen Raumstation zu. Wie die Kommandanten bei allen Kopplungsmissionen steuerte er den Raumgleiter von der hinteren Konsole im Flugdeck aus, weil er von dort freie Sicht auf die Raumstation hatte. Ohne Probleme konnte er sein Raumschiff an die ISS ankoppeln.

Nach den üblichen Dichtigkeitstests konnte die beiden Kommandanten Steven Lindsey (STS-121) und Pawel Winogradow (ISS Expedition 13) die Luken zwischen den Raumfahrzeugen öffnen. Nach einer kurzen Begrüßung und einer Sicherheitseinweisung wurde der vom Shuttle mitgebrachte Schalensitz von Thomas Reiter in dem russischen Sojus-Raumschiff Sojus TMA-8 installiert. Dies geschah zunächst nur als Vorsichtsmaßnahme für den Fall einer überhasteten Rückkehr vor Abholung durch das nächste Space Shuttle. Damit gehörte er offiziell zur Besatzung der Raumstation.

Das Multi-Purpose Logistics Module Leonardo wurde an den Unity Knoten der Raumstation angekoppelt. Es beinhaltete über drei Tonnen Güter, Ausrüstungsteile und Experimente, die von der 13. Stammbesatzung der ISS dringend gebraucht wurden. Später begannen die Astronauten mit dem Entladen des Containers. Dies dauerte mehrere Tage.
Im weiteren Verlauf des Tages widmeten sich die Missionsspezialistinnen Lisa Nowak und Stephanie Wilson zusammen mit Pilot Mark Kelly einer weiteren vierstündigen Überprüfung der Hitzeschutzkacheln des Orbiters. Auf dem Programm standen ausgewählte Gebiete, die beim ersten Scan aufgefallen waren. Darunter die Flügelvorderkanten und die hervorstehenden Füllstreifen.
Die Flugleitung gab eine Verlängerung des Fluges um einen Tag bekannt. Dadurch sollte in einem dritten Außenbordeinsatz der Hitzeschutzschild inspiziert und die Füllstreifen gegebenenfalls entfernt werden.

Die erste EVA unternahmen Piers Sellers und Michael Fossum am 08. Juli 2006 (7h 31m). Hauptaufgabe der EVA war, ein beschädigtes Kabel des Mobilen Transporters zu ersetzen. Außerdem wurde der Robotarm (RMS) des Orbiters mit dem Inspektionsarm (OBSS) verbunden - wie bereits zur Überprüfung des Kachelzustands geschehen. Die NASA wollte so erfahren, ob das 30 Meter lange RMS/OBSS-System stabil genug ist, um Astronauten tragen zu können und im Fall einer Kachelreparatur als Arbeitsplattform zu dienen. Gesteuert von Lisa Nowak und Stephanie Wilson aus dem Shuttle-Cockpit, stieg erst Piers Sellers auf die Plattform am Ende des OBSS. Später kam Michael Fossum dazu, der zunächst alles aus der Nutzlastbucht beobachtet hatte. Entgegen den Erwartungen der Ingenieure, wurden auftretende Schwingungen sehr schnell gedämpft. Die Verbindung von RMS und OBSS scheint also stabil genug für Arbeiten zu sein.

Die zweite EVA erfolgte ebenfalls durch Piers Sellers und Michael Fossum am 10. Juli 2006 (6h 47m). Zunächst hoben die beiden Astronauten eine Ammoniakpumpe (sie wird für das Kühlsystem der Raumstation benötigt) aus dem Frachtraum der Raumfähre und verstauten sie im "Ersatzteillager" der ISS. Es handelt sich um ein Reservegerät, das erst gebraucht wird, wenn die ISS weiter ausgebaut ist. Hauptaufgabe des Ausstiegs war jedoch das Auswechseln eines Fernseh- und Datenkabels, das für die Funktion des ISS-Transportwagens - Mobile Transporter (MT) - wichtig ist. Er wird verwendet, um den Greifarm der Station an seine Einsatzorte zu bringen. Der Wagen war vor sieben Monaten ausgefallen, als eine Trennvorrichtung im MT eines der beiden Datenkabel durchschnitt.

Auch die dritte und letzte EVA wurde durch Piers Sellers und Michael Fossum am 12. Juli 2006 (7h 11m) zur Demonstration von Techniken zur Reparatur eines Hitzeschildes im Orbit ausgeführt. Nachdem sie eine Fußhalterung am ISS-Greifarm montiert hatten, machte sich Piers Sellers daran fest und ließ sich über die Nutzlastbucht der Raumfähre hieven. Mit einer Infrarotkamera fertigte er Einzelbilder sowie einen 20-Sekunden-Film der Flügelvorderkanten an. Mit Hilfe dieser Aufnahmen wollen die NASA-Ingenieure Beschädigungen aufspüren, die oberflächlich nicht zu entdecken sind. Für die Simulation von Reparaturtechniken befand sich in der Nutzlastbucht eine Palette mit einem Dutzend präparierter Kacheln. Michael Fossum und Piers Sellers experimentierten mit dem speziellen Kleber, um festzustellen, wie gut sich dieser unter Weltraumbedingungen auftragen und verteilen lässt. Danach wurden auch von den Testkacheln Infrarotaufnahmen gemacht. Zum Vergleich fertigten die Astronauten sowohl von den behandelten als auch von den unbehandelten Fliesen Fotos und einen einminütigen Film an.

Nachdem das Logistikmodul MPLM Leonardo entladen und mit zur Erde zurückzubringenden Ausrüstungsgegenständen, Abfall und Experimentproben befüllt wurde, wurde es von Lisa Nowak und Stephanie Wilson von der ISS abgekoppelt und mit dem Greifarm der Station in die Nutzlastbucht der Discovery zurückgeführt. Dort wurde das Modul per Fernsteuerung für den sicheren Heimflug zur Erde befestigt.

Am 15. Juli 2006 koppelte die Discovery-Besatzung mittels Federkraft wieder von der ISS ab. Dadurch werden Beschädigungen oder Verunreinigungen der Station vermieden. Erst danach wurden die Steuerungstriebwerke aktiviert und die Raumfähre entfernte sich von ihr bis zu einer Distanz von etwa 150 Meter, ehe die Triebwerke der Discovery erneut gezündet wurden und der Raumgleiter seine Distanz vergrößerte. Eine Umfliegung der Raumstation war nicht geplant. Der Orbiter stoppte dann in einer Entfernung von etwa 75 Kilometer. Mit Hilfe des OBSS wurde eine letzte Überprüfung des Hitzeschutzschildes vorgenommen. Im Notfall hätte das Space Shuttle zur Internationalen Raumstation zurückkehren können.

Zunächst sollte Kommandant Steven Lindsey die Discovery auf Bahn 33 des Kennedy Space Center landen. Südlich des KSC hatte sich jedoch zehn Minuten nach Beginn des Wiedereintritts ein Regengebiet formiert. Daher ordnete das Kontrollzentrum während des Landeanflugs den Wechsel auf die einige Dutzend Kilometer nördlichere Route an. Die Discovery flog das KSC von Südwesten an. Zur Vernichtung der kinetischen Energie beschrieb sie etwa fünf Minuten vor dem Aufsetzen eine langgezogene Linkskurve. Dort, wo die Fähre ursprünglich diese Kurve hätte fliegen sollen, regnete es. Deshalb entschied die NASA, die Landebahn von Norden anfliegen zu lassen. Das KSC verfügt nur über eine Landebahn. Wird die Piste aus südlicher Richtung angeflogen (330°) ist es die Bahn 33, schwebt der Shuttle von Norden ein (150°) nennt man sie Bahn 15.

Thomas Reiter ist am 22. Dezember 2006 um 22:31:58 UTC mit STS-116 gelandet.