Jedným z jeho prvých rýchlostných leteckých rekordov bol ten z 26. novembra 1999, keď na trase merajúcej 2 000 kilometrov dosiahol v lietadle triedy H rýchlosť 962, 81 kilometrov za hodinu. Svetové rekordy vytvoril aj v roku 2000, keď v lietadle, tiež triedy H smerom na východ (tzv. Eastbound) dosiahol 16. februára 2000 rýchlosť 901,07 kilometrov za hodinu a potom 24. novembra 2000 smerom na západ (tzv. Westbound) rýchlosť 805,59 kilometrov za hodinu. Medzitým sa do histórie letectva zapísal aj rekordom z 23. marca 2000, keď z Los Angeles (Kalifornia) doletel do Honolulu na Havaji za 4 hodiny, 11 minút a 5 sekúnd. Dosiahol vtedy rýchlosť 981, 44 kilometrov za hodinu. O pár mesiacov neskôr, presne 14. júla, dosiahol na vzdialenosti 5 000 kilometrov rýchlostný rekord v triede H – 921,02 kilometrov za hodinu. Úspešný bol pre neho aj rok 2001. Z austrálskeho Perthu do Brisbane letel rýchlosťou 1 134,69 kilometrov za hodinu, čím 28. júla 2001 vytvoril austrálsky transkontinentálny rekord. O dva dni neskôr už letel z Perthu do Hobartu rýchlosťou 1 194,17 kilometrov za hodinu, čím vytvoril nový svetový rýchlostný rekord subsonického (podzvukového) lietadla.
Steve Fossett pokračoval vo svojom ťažení na oblohe ďalej 8. októbra 2003, keď sa podpísal pod nový transatlantický rekord v lete podzvukových lietadiel. Prekonal pritom vzdialenosť medzi Goose Bay v Kanade a Berlínom. Rýchlosť uvádzaná pri tomto rekorde je 1 045, 97 kilometrov za hodinu.
Ako letcovi sa mu len v období od februára 2005 do marca 2006 podarilo vytvoriť hneď tri unikátne rekordy. Ako prvý človek uskutočnil sólový let v lietadle, keď štartoval v Saline (Kansas), kde aj o 67 hodín 1 minútu a 10 sekúnd pristál. Fossett opúšťal štartovaciu plochu 28. februára a vrátil sa 3. marca 2005, pričom preletel 36 912,68 kilometrov. Následne vytvoril rekord v najdlhšom prelete v leteckej histórii, keď bol vo vzduchu viac ako 41 467 kilometrov. Štartoval 8. februára 2006 v Kennedyho vesmírnom centre v Cape Canaveral na Floride a pristál 11. februára po 76 hodinách 42 minútach a 55 sekundách v anglickom Bournemouthe. V polovici marca toho istého roka si na svoje konto pripísal absolútny vzdialenostný rekord na uzavretom okruhu, keď letel aj pristával v kansaskom meste Salina. Preletel vtedy spolu 40 707 kilometrov.
Fossett na seba strhol pozornosť aj americkými rekordmi, ktoré vytvoril pri transkontinentálnych letoch. Prvý padol 17. septembra 2000, keď letel z Jacksonvillu v Tennessee do San Diega v Kalifornii. Tento let z východu na západ trval 3 hodiny 29 minút a 35 sekúnd a Fossett ho zvládol vo viacmotorovom turbovrtuľovom lietadle, pričom letel maximálnou rýchlosťou 952,67 kilometrov za hodinu. Ďalšie dva letecké rekordy vytvoril 5. februára 2003. Prvý, keď pri prelete východ – západ v podzvukovom lietadle letel na trase San Diego – Charleston (Južná Karolína) rýchlosťou 1169,73 kilometrov za hodinu, čím prekonal vlastný rýchlostný rekord o 54,73 kilometra za hodinu. Ten vytvoril 6. apríla 2000 na trase San Francisco (Kalifornia) – New York City. Letel vtedy 2 hodiny, 56 minút a 20 sekúnd. V ten istý deň stihol aj ďalší rekord, keď na viacmotorovom turbovrtuľovom lietadle letel zo San Diega do Charlestonu 3 hodiny 51 minút a 52 sekúnd. Vtedy letel rýchlosťou 879,46 kilometrov za hodinu.
K týmto leteckým počin pridal aj ďalšie rekordy z oblasti lietania v balóne. Do dnešných dní vytvoril šesť sólových svetových rekordov v tejto náročnej disciplíne. Na prvý si siahol po úspešnom pokuse, ktorý začal 8. januára 1996. Do 11. januára preletel rekordnú vzdialenosť, približne 3 540 kilometrov pri lete zo Stratobowlu (Južná Dakota) do St. John v Kanade. Nadviazal naň, keď zo St. Louis (Missouri) letel do indického Sultanpuru 6 dní 2 hodiny a 44 minút. V dňoch od 13. do 20. januára teda preletel 16 093,44 kilometrov. Vyšiel mu aj pokus z 1. až 5. januára 1998, keď preletel zo St. Louis do Grečanaje v Rusku vzdialenosť 8 046, 72 kilometra.
V auguste toho istého roka médiá informovali, že trasu Mendoza (Argentína) – Koralové more (severovýchodne od Austrálie) zvládol za deväť dní. Vzdialenosť 22 910 kilometrov pokoril v dňoch od 7. do 16. augusta. Svetový rekord vytvoril Fossett následne v dňoch od 5. do 17. augusta 2001. Z Northamu priletel do Bagé v Brazílii po 12 dňoch, 12 hodinách a 57 minútach vo vzduchu. To ale nikto netušil, že o rok sa z neho stane prvý človek, ktorý úspešne obletí svet a tým vytvorí ustanovujúci svetový rekord. Fossett štartoval 19. júna 2002 v Northame (Západná Austrália) a po 14 dňoch, 19 hodinách a 50 minútach pristál v austrálskom Queenslande 4. júla. Preletel vtedy 33 195,10 kilometrov. Okrem toho počas letu vytvoril aj rýchlostný rekord, keď počas 24 hodín z 30. júna na 1. júla prekonal vzdialenosť 5 128,65 kilometrov. Balón, ktorý takto vstúpil do histórie, sa volal Bud Light Spirit of Freedom. Počas letu dosiahol tiež rekordnú rýchlosť, keď za hodinu preletel 321,86 kilometrov. Ako prvému sa mu tiež podarilo preletieť ponad hranice Ázie, Afriky, Európy a Južnej Ameriky a zároveň počas toho istého letu prekonať južný Atlantik, južnú oblasť Tichého oceánu a Indický oceán. Rozhodne to ale neboli jediné jeho rekordy, ktoré v lietaní balónom dosiahol.
Skúsený Fossett je aj autorom desiatich svetových rekordov v lietaní na vetroňoch. Jeden vytvoril v roku 2002, osem v roku 2003 a posledný v roku 2004. Pamätný prvý – 12. decembra 2002 s Novozélanďanom Terrym Delorom, s ktorým vytvorili aj všetky ostatné, posledný 4. decembra 2004. Fossett vyskúšal aj lietať na vzducholodi. Absolútny rýchlostný rekord v lietaní vzducholodí vytvoril v Nemecku 27. októbra 2004 na vzducholodi menom Zeppelin NT Friedrichshafen, keď išiel rýchlosťou asi 111,8 kilometra za hodinu.
Okrem lietania mu učarovalo aj moreplavectvo, v ktorom vytvoril 21 svetových rekordov. Príkladom môže byť jeho plavba okolo Írska 8. a 9. septembra 1993 za 44 hodín a 42 minút, alebo iná, keď sa od 22. júla do 4. augusta 1995 plavil z Havaja do Japonska. V roku 1996 zasa svetobežník prekonal na lodi vzdialenosť od východného po západné pobrežie Tichého oceánu. Zo San Francisca (Kalifornia) vyplával 3. mája a v Jokohame zhodil kotvy 23. mája. Po dlhšej prestávke zapísal ďalší rekord do análov moreplavectva 14. januára 2000, keď mu stačili dva dni na to, aby preplával vzdialenosť medzi Newportom a Bermudami. Z New Yorku do Anglicka sa zasa plavil 5. až 10. októbra 2001 po mori 4 dni, 14 hodín, 28 minút a 6 sekúnd, čím vytvoril nový transatlantický rekord. Medzi jeho významné rekordy v tejto športovej disciplíne patrí aj plavba naprieč Stredozemím, keď 23. a 24. mája 2002 pokoril vzdialenosť medzi francúzskym prístavným mestom Marseille a tuniským Kartágom za 18 hodín, 46 minút a 48 sekúnd. Do britských vôd sa na 4 dni, 16 hodín, 9 minút a 36 sekúnd vrátil aj v októbri 2002. Okolo sveta sa plavil aj od 7. februára do 5. apríla 2004. Predošlý rekord v rýchlosti oboplávania zemegule pokoril o 6 dní. Cesta mu trvala 58 dní, 9 hodín, 32 minút a 45 sekúnd.
Jeho osobný profil dotvárajú aj ďalšie ocenenia, ktoré kompletne zverejnila internetová stránka www.stevefossett.com. Ako informuje, Fossett sa v minulosti zúčastnil aj musherských pretekov Iditarod (47. miesto, 1992), súťaže Železný muž (1996), preplával La Manche (1985), a súťažil v cross-country lyžovaní.
Steve Fossett získal v minulosti niekoľko prestížnych ocenení. Od Medzinárodnej Aeronautickej federácie (FAI) to boli Diplôme de Montgolfier (1996), Prix De La Vaulx (1995, 1997,1998, 2002, 2004), Gold Air Medal (2002), Centenary Medal (2005) a Tissandia Diploma (2005). Od Národnej aeronautickej asociácie (NAA) dostal Harmon Trophy (1998, 2002), od francúzskej Akadémie športov (AS) Prix de l'Aventure Sportive (2002). Francúzska republika mu udelila Medaille de l'Aéronautique (2003), Americká plachtárska asociácia (US SA) zasa titul Rolex Yachtsman of the Year (2001), Britský kráľovský aeroklub (RAC UK) prestížnu Gold Medal (2002), National Geographic Society zasa cenu Distinction in Exploration (1998) a dve ceny – Distinguished Eagle Scout a Silver Buffalo (1998, 1999) získal od Amerického chlapčenského skautingu.
Steve Fossett získal aj dva čestné doktoráty a oba v máji 2006 – na Ripon College a Washington University. Je tiež čestným členom Francúzskeho aeroklubu, Írskeho národného jachtárskeho klubu a niekoľkých menších.
Naposledy sa o Fossettovi hovorilo v súvislosti s jeho zmiznutím v Nevadskej púšti v pondelok 3. septembra o 8:45 miestneho času (17:45 SELČ). Pátranie po ňom sa začalo po tom, ako sa stratilo jeho lietadlo. Fossetta podľa správ naposledy videli ako odlieta zo súkromnej štartovacej plochy Flying M Ranch neďaleko Yeringtonu v Nevade. Cestovateľ letel v modro-bielom jednomotorovom lietadle Citabria Super Decathlon. Záchranárov zalarmovali po tom, ako Fossettova rodina nahlásila, že sa nevrátil z výletu, ktorý mal trvať iba niekoľko hodín. Nezvestný je dodnes.