בשנת 1996, בעזרת שיתוף פעולה בין תומאס ויזל לאדי בוריסוויץ, הוקמה הקבוצה מחדש תחת חסות רשות הדואר של ארצות הברית, ושם הקבוצה שונה ל"קבוצת רכיבת האופניים המקצוענית של רשות הדואר האמריקאית" (US Postal Service Pro Cycling Team). בוריסוויץ שימש כמנהל הספורטיבי של הקבוצה. קבוצת רשות הדואר הייתה קבוצת האופניים הגדולה בארצות הברית, והיא השתתפה בראשית דרכה בעיקר במרוצים ואירועים מקומיים בארצות הברית. ההישג הגדול ביותר של הקבוצה החדשה בשנה הראשונה שלה היה זכייתו של אדי גראגוס, הרוכב המוביל שלה באותו זמן, באליפות ארצות הברית.
ב-1997 ויזל הביא לקבוצת רשות הדואר את מארק גורסקי, זוכה מדליית זהב באולימפיאדת 1984, בתור המנהל הספורטיבי והמאמן החדש של הקבוצה. באותה שנה אף הצטרפו לקבוצה ויאצ'סלב אקימוב הרוסי, וג'ורג' הינקאפי, שהיה מבכירי הרוכבים הצעירים בארצות הברית. בעיקר הודות לניצחונותיו של אקימוב בקטעים במרוצים החשובים פריז - ניס ודופינה ליברה, קיבלה קבוצת רשות הדואר לראשונה זימון להשתתף באותה שנה בטור דה פראנס, מרוץ האופניים הגדול בעולם. הרוכב הבכיר של הקבוצה בטור הראשון שלה היה ז'אן-סיריל רובין, שסיים במקום ה-15.
בשנת 1998 חתם ברשות הדואר לאנס ארמסטרונג, שהחלים זה עתה מסרטן האשכים חמור וחזר לרכיבה מקצוענית. המהלך בוצע בתום משא ומתן מתמשך בין תומאס ויזל והנהלת הקבוצה לבין סוכנו של ארמסטרונג. בעברו, רכב ארמסטרונג גם עבור קבוצת סובארו מונטגומרי שהובלה על ידי ויזל, לפני הקמת קבוצת רשות הדואר. מלבד ארמסטרונג הצטרף לקבוצה באותה שנה רוכב אמריקאי בכיר נוסף, פרנקי אנדרו. הרוכבים האמריקאים הבכירים של קבוצת רשות הדואר זכו במספר מרוצים פחותי-חשיבות במהלך השנה: ארמסטרונג זכה בשנה הראשונה שלו מאז חזרתו בטור של לוקסמבורג ובמרוץ בריינלנד-פפאלץ, ואנדרו זכה במירוץ בלנקסטר. באליפות ארצות הברית באותה שנה זכה ג'ורג' הינקאפי, בעוד שארמסטרונג סיים במקום הרביעי.
קבוצת רשות הדואר עברה שדרוג נוסף לקראת עונת המרוצים של 1999, כאשר החתימה את רוכב העבר הבלגי, יוהאן ברוינל, בתור מנהלה הספורטיבי. הקבוצה הייתה מחוזקת במספר רוכבים כישרוניים שהצטיינו בטיפוסים, כמו קווין ליווינגסטון שהצטרף אליה באותה שנה, טיילר המילטון וכריסטיאן ואנדוולדה, נוסף על ג'ורג' הינקאפי. שני הרוכבים המובילים של הקבוצה היו לאנס ארמסטרונג ופרנקי אנדרו. לאורך כל השנה התאמנה הקבוצה כולה רבות בהרי האלפים והפירינאים תחת הדרכתו של ברוינל, כשמטרתה הייתה לסייע לארמסטרונג לזכות בטור דה פראנס בחודש יולי. הקבוצה הייתה אנונימית למדי לקראת הטור דה פראנס, והפרשנים לא ציפו לניצחונה. אף על פי כן, הרוכבים הכישרוניים סייעו לארמסטרונג בהתמודדות בהרים עם רוכבי הקבוצות האחרות החזקות, וארמסטרונג זכה בצורה מפתיעה בטור דה פראנס. זכייה זו הביאה את קבוצת רשות הדואר לתודעה העולמית, ואף הגדילה מאוד את תקציבה כתוצאה מחשיפה באמצעי התקשורת.
בשנת 2000 הקבוצה המשיכה את הצלחותיה. שני רוכבי הקבוצה, לאנס ארמסטרונג וויאצ'סלב אקימוב, זכו במשותף ב"גרנד פרי אדי מרקס" - מרוץ זוגי נגד השעון על שמו של רוכב העבר אדי מרקס. בחודש יולי זכה לאנס ארמסטרונג בפעם השנייה ברציפות בטור דה פראנס, בעזרתם הרבה של הרוכבים המצטיינים הבכירים בקבוצה. הייתה זו הפעם הראשונה בה גבר ארמסטרונג על יאן אולריך, שנעדר מהמרוץ ב-1999 ונחשב כיריבו הגדול של ארמסטרונג. קבוצת רשות הדואר התמקדה שוב בעיקר בטור דה פראנס, ועל כן לא הגיעה באותה שנה להישגים משמעותיים רבים נוספים מלבד הזכייה בטור. באולימפיאדת סידני זכה ויאצ'סלב אקימוב במדליית הזהב במרוץ נגד השעון, וארמסטרונג זכה בו במדליית הארד.
ב-2001 הוחתמו ברשות הדואר שני רוכבים מוכשרים נוספים שנועדו לעזור לארמסטרונג בטור דה פראנס: רוברטו הראס הספרדי וויקטור הוגו פנייה הקולומביאני, וכמו כן הצטרף חוסה לואיס רוביירה הצעיר שהיה עתיד להיות אחד מהעוזרים המנוסים והחשובים בקבוצה. מנגד, עזבו את הקבוצה בעונה זו שלושה מהרוכבים החשובים שלה: פרנקי אנדרו (מוביל הקבוצה יחד עם ארמסטרונג), טיילר המילטון שעבר לקבוצת CSC, וקווין ליווינגסטון שעבר לדויטשה טלקום. במהלך השנה זכה ג'ורג' הינקאפי במרוץ גנט - וולגם בבלגיה, וכמו כן רוברטו הראס זכה בוואלטה קטלוניה. בטור דה פראנס סייעה הקבוצה ללאנס ארמסטרונג לסגור פער של 35 דקות בדירוג הכללי מהמוביל פרנסואה סימון (ולזכות לבסוף במרוץ). הייתה זו סגירת הפער הגדולה ביותר בתולדות הטור. בספטמבר סיים רוברטו הראס במקום הרביעי בוואלטה אספניה, אחד משלושת הגרנד טורס. בסוף 2001 קבוצת רשות הדואר נבחרה לקבוצת הספורט של השנה מטעם הוועד האולימפי האמריקאי.
קבוצת רשות הדואר זכתה להישגים רבים בעונת המרוצים של 2002. בשנה זו הצטרף לקבוצה פלויד לאנדיס הצעיר, שהתפתח והתקדם רבות מבחינה מקצועית כתוצאה מעזרתו והדרכתו של לאנס ארמסטרונג. בדופינה ליברה, מרוץ ההכנה החשוב ביותר לטור דה פראנס, זכה ארמסטרונג, ולאנדיס סיים במקום השני. ויקטור הוגו פנייה זכה בחודש יולי במרוץ וואלטה מורסיה בספרד. כמו בשנים קודמות, הפגינה קבוצת רשות הדואר שליטה מרשימה בקטעים ההרריים של הטור דה פראנס באותה שנה, וכונתה "הרכבת הכחולה" בעקבות הטקטיקה אותה יישמה. היא סייעה לארמסטרונג לזכות בפעם הרביעית ברציפות בטור דה פראנס, בפער של 7 דקות מחוסבה בלוקי שבמקום השני. הקבוצה סיימה במקום השני בדירוג הכללי הקבוצתי של המרוץ. בסוף העונה סיים רוברטו הראס במקום השני בוואלטה אספניה, הישג שנחשב כאכזבה מסוימת שכן הראס נחשב כמועמד הבכיר לניצחון והוביל את המרוץ עד לקטע האחרון שבו.
הקבוצה פתחה בצורה מצוינת גם את הטור דה פראנס ב-2003. הקבוצה ניצחה את הקטע הרביעי, שהיה קטע קבוצתי נגד השעון, ותפסה למשך שלושה קטעים את כל שמונה המקומות הראשונים בדירוג הכללי, כאשר ויקטור הוגו פנייה במקום הראשון. בקטע השביעי איבד פנייה את ההובלה לרישאר ויראנק מקבוצת קוויק סטפ, אך בקטע שלאחר מכן נטל לאנס ארמסטרונג את ההובלה. בתום מרוץ רצוף תקריות ותאונות, הצליח ארמסטרונג לזכות בפעם החמישית ברציפות בטור, והפך לאחד מחמישה רוכבים בלבד שעשו זאת. בדירוג הקבוצתי סיימה קבוצת רשות הדואר במקום הרביעי. לאחר הטור דה פראנס הגיעה הקבוצה להישג גדול נוסף - רוברטו הראס זכה בוואלטה אספניה, והביא לקבוצה ניצחון שני בגרנד טור באותה עונה, וניצחון בגרנד טור שני בסוגו בתולדותיה.
בעונת 2004, עזבו את רשות הדואר רוברטו הראס וכריסטיאן ואנדוולדה, שניים מהרוכבים החשובים בקבוצה. הקבוצה צירפה את ז'וזה אזוודו, אך מלבדו לא החתימה מחליפים משמעותיים לשני רוכבים אלו. התואר הראשון של הקבוצה בשנה זו היה במרוץ שלושת הימים של דה פאן בחודש אפריל, בו זכה הינקאפי. באותו חודש זכה ארמסטרונג בטור של ג'ורג'יה, ובנוסף זכה לאנדיס באותה שנה בוואלטה אלגארבה. בטור דה פראנס ניצחה רשות הדואר בפעם השנייה ברציפות את הקטע הקבוצתי נגד השעון. לאנס ארמסטרונג, שניצח גם בחמישה קטעים, זכה במרוץ בסופו בפעם השישית ברציפות, וקבע שיא זכיות בטור דה פראנס. בנוסף, ז'וזה אזוודו סיים במקום החמישי בדירוג הכללי.
דיסקברי צ'אנל (2005-2007).
ב-2005 הפסיקה רשות הדואר של ארצות הברית את החסות שנתנה לקבוצה, והספונסר החדש של הקבוצה היה ערוץ דיסקברי. שם הקבוצה שונה ל"קבוצת רכיבת האופניים המקצוענית של ערוץ דיסקברי". בעונת המרוצים של 2005 החלה קבוצת דיסקברי צ'אנל להתחרות בסבב ה"פרו טור של ה-UCI", שהחל לפעול באותה שנה והחליף את סבב הגביע העולמי באופני כביש. בעונה זו הצטרפו פאולו סבולדלי וירוסלב פופוביץ' הצעיר לחיזוק הקבוצה, אך פלויד לאנדיס עזב אותה בעקבות הצעה שקיבל מקבוצת פונאק. בחודש מאי זכה סבולדלי בג'ירו ד'איטליה, המרוץ השני בחשיבותו בעולם. הייתה זו הזכייה הראשונה של הקבוצה במרוץ זה. בטור דה פראנס, ניצחה הקבוצה את הקטע הקבוצתי נגד השעון במהירות של 57.32 קמ"ש, ובכך קבעה את התוצאה הטובה ביותר בהיסטוריה של האירוע. לאנס ארמסטרונג זכה בפעם השביעית ברציפות בטור דה פראנס, לאחר שהוביל לאורך רוב המרוץ. ירוסלב פופוביץ' זכה בתואר הרוכב הצעיר המצטיין במרוץ.
לאנס ארמסטרונג פרש מרכיבה לאחר זכייתו השביעית בטור דה פראנס, והפך לחלק מהצוות המקצועי של הקבוצה. בפתיחת שנת 2006 הצטרף לקבוצה אגוי מרטינס הספרדי. התואר הראשון של דיסקברי צ'אנל בשנה זו היה במרוץ שלושת הימים של דה פאן, בו זכה לייף הוסט הבלגי. בחודש מאי סיים פאולו סבולדלי, הרוכב הבכיר של הקבוצה, במקום החמישי בג'ירו ד'איטליה. בטור דה פראנס של 2006, הראשון של דיסקברי מאז פרישת ארמסטרונג, נכשלה הקבוצה. הרוכב המצליח של הקבוצה בטור זה היה ז'וזה אזוודו, שסיים במקום ה-18 בלבד. סבולדלי, שסיים חמישי בג'ירו ד'איטליה, נעדר מהטור דה פראנס בשל תאונה. הקבוצה סיימה שמינית בלבד בדירוג הקבוצתי. בחודש ספטמבר, לאחר הטור דה פראנס, זכה ג'ורג' הינקאפי באליפות ארצות הברית. בוואלטה אספניה זכתה הקבוצה להצלחה חלקית לאחר שרוכביה ניצחו בשני קטעים, מרטינס ניצח בקטגוריית ההרים והקבוצה סיימה במקום הראשון בדירוג הקבוצתי במרוץ.