Der Weg von STS-80 in die Umlaufbahn begann von Cape Canaveral (KSC) und die Landung erfolgte ebenso auf Cape Canaveral (KSC), Runway 33.

Der Start war ursprünglich für den 31. Oktober 1996 geplant. Aus verschiedenen Gründen wurde der Starttermin aber auf den 19. November 1996 neu festgesetzt. So mussten die äußeren 1,6 Zentimeter dicken Scheiben der Columbia ausgetauscht werden, weil die NASA-Ingenieure ein Zerbrechen nach mehreren Raumflügen befürchteten. Außerdem hatten Techniker in der Isolierschicht auf der Innenseite der Booster-Düsen Furchen entdeckt, die ausgebessert werden mussten. Am Starttag selbst kam es noch wegen vorübergehend aufgetretener zu hoher Wasserstoffkonzentration im Heck der Columbia für gut zweieinhalb Minuten eine Unterbrechung des Countdowns.

Zu den wesentlichen Missionszielen gehörte das Aussetzen und Wiedereinfangen des deutschen Astronomie-Satelliten ORFEUS-SPAS-02 sowie des Freiflugkörpers "Wake Shield Facility" (WSF-3). Damit sollten zum ersten Mal von einer Raumfähre zwei Freiflugeinheiten gleichzeitig überwacht werden. Geplant waren auch zwei Außenbordeinsätze im Rahmen des EDFT-Programmes. STS-80 war mit einer "Extended Duration Orbiter" (EDO)-Palette ausgerüstet, die es erlaubt, Flüge mit längerer Missionsdauer zu unternehmen. Um einen Orbiter für längere Flüge umzurüsten, waren interne Änderungen und die Installation der EDO-Palette in der Nutzlastbucht erforderlich. Mit ihr kann eine Missionsdauer von bis zu 16 Tagen zuzüglich zwei Ausweichtagen erreicht werden. Der Unterschied zwischen einem normalen Orbiter und einem EDO besteht im Wesentlichen aus zusätzlichen Wasserstoff- und Sauerstofftanks, die auf der EDO-Palette montiert sind, und zusätzlichen Systemen zum Luftreinigungs- und Abfallsystem. Die EDO-Palette wiegt etwa 1.575 kg, hat einen Durchmesser von ungefähr 4,5 Metern und wird am hinteren Ende der Nutzlastbucht montiert.

Gleich nach dem Erreichen der Erdumlaufbahn und dem Öffnen der Frachtraumtüren begannen die Vorbereitungen für das Aussetzen der deutschen Forschungsplattform ORFEUS-SPAS-02. ORFEUS ("Orbiting and Retrievable Far and Extreme Ultraviolet Spectrograph") ist ein Komplex astronomischer Instrumente, die auf einem Palletten-Satelliten (SPAS) montiert sind. Hauptnutzlast sind das 1-Meter-Spiegelteleskop (Brennweite 2,4 Meter) und zwei UV-Spektrographen, der "Far Ultraviolet Spectrograph" für Wellenlängen im Bereich 90 - 125 nm sowie der "Extreme Ultraviolet Spectrograph", der Licht mit Wellenlängen von 40 bis 115 nm untersucht. Damit wurden die Oberflächen besonders großer und heißer Sterne, die Koronen sonnenähnlicher Sterne, die Kühlmechanismen weißer Zwergsterne, die Natur von Akkretionsscheiben um kollabierte Sterne und Doppelsternsysteme, Supernova-Überreste, aktive Galaxien, interstellare Materie und potentielle Sternentstehungsgebiete untersucht. ORFEUS war bereits mit dem Flug von STS-51 im Weltraum gewesen.
Die Freiflugplattform wurde mit dem Greifarm der Columbia aus dem Frachtraum herausgehoben und auf eine eigenständige Umlaufbahn ausgesetzt. Zwei Zündungen der Lagekontrolldüsen sorgten dafür, dass sich die Entfernung der beiden Raumflugkörper vergrößerte. Etwa drei Stunden nach dem Aussetzen öffnete sich der Schutzdeckel von ORFEUS und die astronomischen Beobachtungen konnten beginnen.

Am vierten Flugtag stand das Aussetzen des Freiflugkörpers "Wake Shield Facility" (WSF-3) auf dem Arbeitsprogramm der Besatzung. Der vorausfliegende Schild der WSF hat einen Durchmesser von etwa 3,6 Metern und erzeugt in seinem Schatten ein besonders gutes Vakuum. Es ist 100 bis 1000 Mal reiner als das beste künstlich erzeugte Vakuum auf der Erde. Hier wurden epitaktisch sieben dünne Filme (sogenannte Wafer) aus Mischhalbleitermaterialien, beispielsweise Aluminium-Galliumarsenid und Indium-Galliumarsenid, hergestellt. Obwohl es sich bereits um den dritten Einsatz der WSF handelte, wurde der Freiflug dadurch schwieriger, dass mit ORFEUS-SPAS-02 bereits ein Satellit unterwegs und zu überwachen war. Geplant war, die drei Raumflugkörper in der Reihenfolge Columbia, WSF und ORFEUS-SPAS-02 in einem Abstand von jeweils 40 Kilometern etwa auf der gleichen Umlaufbahn fliegen zu lassen.
Thomas Jones begann den Aussetzvorgang mit der Aktivierung des Shuttle-Greifarms. Nach erfolgreichen Tests packte er die WSF an ihrem Greifstutzen und brachte sie in die sogenannte "Ram Cleaning Position", die sich seitlich vom Frachtraum noch vor der linken Tragfläche befand. Dann drehte er die Seite mit den Experimenten so in Flugrichtung, dass sie voll vom dünnen Strom der Gasmolekühle der Restatmosphäre getroffen wurde. Nachdem die WSF so von möglichen Verunreinigungen befreit worden war, manövrierte Thomas Jones den scheibenförmigen Satelliten in großem Bogen auf die gegenüberliegende Seite der Columbia. Danach brachte er sie in Aussetzposition direkt über dem Frachtraum. Schließlich gab Thomas Jones die WSF frei. Der zweite Alleinflug einer WSF hatte begonnen. Zunächst hatte sich bei ihr eine ungeplante Drehbewegung eingestellt, die aber durch die Zündung der WSF-Kaltgas-Triebwerke rasch gestoppt wurde. Mit weniger als 3 Metern Abstand, geplant waren 6 - 8 Meter, flog die WSF über die Mannschaftskabine hinweg. Kommandant Kenneth Cockrell stand aber in Bereitschaft, zur Vermeidung einer Kollision die Lageregelungstriebwerke der Columbia zu zünden. Die dadurch hervorgerufene Verschmutzung der Freiflugplattform hätte aber zu einem Scheitern dieser WSF-Mission geführt.

Beide Satelliten selbst funktionierten einwandfrei. Mühe bereitete den Astronauten und der Missionsleitung am Boden der geplante Formationsflug. Für die Bergung der WSF bedeutete ein geringer gewordener Abstand zwischen den drei Raumflugkörpern insofern ein Problem, als der notwendige Sicherheitsabstand zu ORFEUS-SPAS-02 unterschritten wurde. Um die WSF nicht einen Tag früher als geplant bergen zu müssen, wurde ORFEUS-SPAS-02 für fünf Stunden so gedreht, dass der Satellit kaum noch Widerstand in der Restatmosphäre bot.

Trotzdem entschied die Flugleitung, die WSF drei Erdumkreisungen früher als geplant einzufangen. Mit mehreren Triebwerkszündungen leiteten Kenneth Cockrell und Kent Rominger das Rendezvous ein. Vorgesehen war ein sogenannter "R-Bar Approach", d.h. die Columbia näherte sich der WSF von unten. In 10 Metern Abstand konnte Thomas Jones den Satelliten mit dem Greifarm festhalten und in der Ladebucht verstauen. Am folgenden Tag wurde die WSF für weitere Experimente ("Atomic Oxygen Processing") nochmals aus der Nutzlastbucht herausgehoben, ohne sie jedoch erneut auszusetzen.

Für den 28. November 1996 war der erste von zwei geplanten Außenbordeinsätzen durch Tamara Jernigan und Thomas Jones geplant. Im Rahmen des Programms EDFT sollten sie weitere Übungen und Tests für den Aufbau einer Raumstation ausführen. Insbesondere sollte ein neuartiger Kran ausprobiert werden. In der Luftschleuse der Columbia ließen sie zunächst die normale Atmosphäre ab und wollten dann mit einer Kurbel die äußere Luke öffnen. Zum Öffnen ist mehr als eine Umdrehung der Kurbel (440 Grad) erforderlich, aber schon nach 30 Grad bewegte sich die Kurbel nicht weiter. In den nächsten beiden Stunden versuchten Tamara Jernigan und Thomas Jones vergeblich, die Luke doch noch zu öffnen. Unverrichteter Dinge mussten die beiden Astronauten in die Mannschaftskabine zurückkehren. Die für den 30. November 1996 vorgesehene EVA durch Tamara Jernigan und Thomas Jones wurde dann von der Flugleitung ebenfalls abgesagt.
Eine im Notfall durchzuführende EVA, um den Orbiter "von Hand" für eine sichere Landung vorzubereiten (z.B. Sicherung der Ku-Band-Antenne oder manuelles Schließen der Frachtraumtüren) hätte nicht durchgeführt werden können. Insofern war die klemmende Ausstiegsluke auch ein Sicherheitsproblem. Noch schwieriger wäre es gewesen, wenn sich die Luke nach einer EVA nicht wieder luftdicht hätte verschließen lassen. In dem Fall hätten sich die EVA-Astronauten an das Lebenserhaltungssystem in der Luftschleuse anschließen müssen, um dort eine sofortige Notlandung des Orbiters zu überstehen.
Nach der Rückkehr zur Erde stellte sich heraus, dass in dem Öffnungsmechanismus eine Schraube aus dem Gewinde herausgefallen war. Vorsorglich wurden die Systeme der anderen Raumfähren entsprechend untersucht. Es wurden aber keine weiteren losen Schrauben gefunden.

Am 02. Dezember 1996 entschied die NASA, den Flug von STS-80 um einen Tag zu verlängern. Zugleich wurde auch der Freiflug von ORFEUS-SPAS-02 um einen Tag ausgedehnt.

Für den 03. Dezember 1996 stand nun das Einfangen von ORFEUS-SPAS-02 auf dem Plan. Kenneth Cockrell und Kent Rominger führten einen inzwischen üblich gewordenen "R-Bar Approach" durch. Als der Abstand zu der Freiflugplattform nur noch 10 Meter betrug, konnte Tamara Jernigan sie ohne Probleme mit dem RMS ergreifen. Der Freiflug hatte über 14 Tage gedauert.

In der Ladebucht der Raumfähre waren weitere Apparaturen untergebracht. Damit wurden der Einfluss der Mikrogravitation auf genetisch veränderte Tomaten- und Tabakkeimlinge untersucht. Als molekulare Marker waren mehrere Gene aus Sojabohnen eingepflanzt. Gegenstand der Forschungen waren Transport und Verteilung von Hormonen in den Pflanzen sowie die Geschwindigkeit des Pflanzenwachstums. Insgesamt 200 Keimlinge waren in 22 Petrischalen untergebracht und auf 5 Kanister verteilt ("Biological Research in Canisters"). Zur Analyse auf der Erde wurden einige Pflanzen eingefärbt oder eingefroren.

Zumeist biologisch waren auch die Proben, die im Rahmen eines Bildungsprogrammes an Bord der Columbia waren ("Space Experiment Module"). Schüler verschiedener Altersgruppen hatten die Experimente entworfen und gebaut. So wurden Algen, Knochen, Filmmaterial, Hefe, Krabben, Pflanzensamen, Kalk, Popcorn und Moskitoeier mitgeführt. Anspruchsvollere Untersuchungen beschäftigten sich beispielsweise mit der Konvektion in Flüssigkeiten, der Wärmeleitung in Kupfer, dem Verhalten nicht mischbarer Flüssigkeiten in der Schwerelosigkeit, Messungen von Gravitation und Beschleunigungen sowie dem Studium von Kristallen. Zum Forschungskomplex gehörte auch ein Partikeldetektor.

Bisherige Wärmeaustauschsysteme funktionieren über eine Kühlflüssigkeit, die die überschüssige Wärme aus der Kabine zu Radiatoren transportiert. Der Kühlkreislauf wird dabei von kleinen Pumpen in Gang gehalten. Effektiver könnte jedoch in Zukunft ein System sein, bei dem der Flüssigkeitsstrom motorlos, durch Kapillarkräfte angetrieben wird. Ein entsprechendes System ("Capillary Pumped Loop") wurde während der Mission getestet. Dabei wurde das Verhalten der Flüssigkeit und des entstehenden Dampfes zur genaueren Untersuchung aufgezeichnet.

Wegen einer aufziehenden Schlechtwetterfront wollte die NASA den Flug von STS-80 eigentlich wieder um 24 Stunden kürzen, jedoch gestatteten tiefhängende Wolken am 05. Dezember 1996 keine Landung in Florida. Für den folgenden Tag sah die Prognose noch schlechter aus. In Florida herrschte Bodennebel und auf der Edwards AFB verhinderten starke Winde eine Landung. Notgedrungen musste die NASA die Mission um einen weiteren Tag verlängern. Erst am Morgen des 07. Dezember 1996 konnte die Raumfähre sicher in Cape Canaveral (KSC) landen. Durch die witterungsbedingte Verlängerung wurde es der längste Shuttle-Flug.

Story Musgrave stellte mit STS-80 einen neuen Altersrekord für Raumfahrer auf. Dieser Rekord ist inzwischen gebrochen. Zugleich wurde er der einzige Astronaut, der mit allen fünf Space Shuttle geflogen ist.