קיץ 1998 שם קץ לשרשרת האליפויות של הבולס (6 אליפויות ב-8 שנים). קראוס החליט שהקבוצה מבוגרת מדי וצריכה להיבנות מחדש. הוא שלח את סקוטי פיפן ליוסטון רוקטס בעסקת "החתמה והעברה" (Sign and Trade) בתמורה לרוי רוג'רס ובחירת דראפט עתידית. בנוסף הוא לא החתים את דניס רודמן על הארכת חוזה, והעביר את סטיב קר ולוק לונגלי בתמורה לבחירות דראפט. הוא החתים מאמן חדש, טים פלויד, שהצליח בקריירת אימון המכללות שלו. החמישייה החדשה של הבולס כללה את רנדי בראון, רון הרפר, ברנט בארי, טוני קוקוץ', וביל ונינגטון. בעונה המקוצרת הוביל קוקוץ' את הקבוצה בממוצע נקודות (18.8), אסיסטים (5.3) וריבאונדים (7.0), אך הבולס ניצחו 13 משחקים מתוך 50 ולא העפילו לפלייאוף.
בקיץ 1999 זכו הבולס בבחירה הראשונה של דראפט 1999, שבה הם בחרו באלטון ברנד. אחרי שהרפר, ונינגטון ובארי עזבו כשחקנים חופשיים, הוביל את הבולס ברנד יחד עם רוקי נוסף, רון ארטסט. רנד הוליך את כל שחקני השנה הראשונה בממוצע נקודות (20.1), ריבאונדים (10.0) וחסימות (1.6), וארטסט הוביל את הרוקיז בממוצע חטיפות (1.7) וסיים במקום הרביעי בממוצע נקודות למשחק (12.0). ברנד זכה בתואר רוקי השנה ב-NBA ביחד עם סטיב פרנסיס, וארטסט נבחר לחמישיית הרוקיז השנייה של העונה. למרות ההישגים האישיים הבולס השיגו מאזן שלילי 17–65, השני מהסוף בליגה.
לקראת עונת החתימה שיקגו את הסנטר בראד מילר ואת הקלע רון מרסר. בנוסף הם בחרו בדראפט 2000 את מרכוס פייזר (בחירה רביעית), ואת ג'מאל קרופורד (בחירה שמינית). ברנד הוביל את הקבוצה בנקודות ובריבאונדים בממוצע למשחק, אך הרכישות החדשות לא הצליחו להותיר את חותמם, והבולס סיימו את העונה עם המאזן הגרוע ביותר בליגה, 15–67.
בערב דראפט 2001 הפתיע קראוס את אוהדי הבולס כשהעביר את ברנד, כוכב הקבוצה, ללוס אנג'לס קליפרס בתמורה לבחירה השנייה בדראפט, טייסון צ'נדלר. בנוסף הוא בחר בדראפט את השחקן אדי קרי בבחירה הרביעית. הן צ'נדלר והן קרי דילגו על שלב המכללות ועברו ל-NBA ישירות מליגת התיכונים. הבולס סבלו מחוסר שחקנים ותיקים ומנוסים, ובעקבות זאת הם שלחו את ארטסט, מרסר, מילר וקווין אולי לאינדיאנה פייסרס בתמורה לג'יילן רוז, טרוויס בסט ונורמן ריצ'רדסון. הבולס שיפרו את מאזנם במעט, כשהגיעו למאזן 21–61, אך עדיין החזיקו במאזן הניצחונות הנמוך ביותר בליגה בפעם השנייה ברציפות.
את עונת התחילו הבולס עם אופטימיות גדולה יותר מאשר את העונות הקודמות. הם בחרו בבחירת הדראפט השנייה את הרכז ג'יי ויליאמס. ויליאמס ורוז הצטרפו לקרופורד, פייזר, קרי, צ'נדלר, דונייל מרשל וטרנטון האסל שיצרו קבוצה צעירה ומבטיחה, ושיפרו את מאזן הבולס ל-30–52 בעונת האימון המלאה הראשונה של ביל קרטרייט. קרי הוביל את הליגה באחוזי קליעה מהשדה (58.5%), ובכך הפך לשחקן הבולס הראשון מאז מייקל ג'ורדן שהוביל את הליגה בקטגוריה כלשהי. למרות ההצלחה היחסית לא העפילו הבולס לפלייאוף גם בעונה זו.
במהלך קיץ 2003 התפטר הג'נרל מנג'ר ג'רי קראוס, ובמקומו מונה שחקן העבר של הקבוצה ג'ון פקסון. ג'יי ויליאמס שבא אחרי עונת רוקי מרשימה נפצע קשות בתאונת אופנוע והיה בספק לעונה הבאה. הוא שוחרר בפברואר 2004 מהבולס והוא לא חזר לעולם לשחק כדורסל באופן מקצועי. פקסון בחר בבחירה השביעית של דראפט 2003 עתיר הכוכבים לעתיד את קירק היינריך, והחזיר לקבוצה את סקוטי פיפן שבעבר שיחק לצדו בבולס. על אף הציפיות הגבוהות, עונת הייתה אכזבה גדולה לבולס; אדי קרי נסוג ביכולתו, טייסון צ'נדלר נפצע בגבו ושיחק ב-35 משחקים, והיכולת של פיפן הוגבלה בגלל בעיות בברכו והוא שותף ב-23 משחקים בלבד. המאמן ביל קרטרייט פוטר בנובמבר 2003 והוחלף על ידי סקוט סקיילס, וכחודש לאחר מכן צירפה שיקגו את אנטוניו דייוויס וג'רום ויליאמס בטרייד עם טורונטו ראפטורס, בתמורה לרוז ומרשל. הבולס סיימה את העונה עם מאזן 23–59, השני מהסוף בליגה. חוזהו של פייזר לא הוארך, וחוזהו של קרופורד הוארך אך הוא מיד נשלח לניו יורק ניקס. היינריך הפך לאהוב אוהדי הבולס, ואחד משחקניה היציבים של הקבוצה, ובסיום העונה הוא נבחר לחמישיית הרוקיז של העונה ב-NBA.
2004–2010: החזרה לפלייאוף וההתחזקות.
בדראפט 2004 קיבלו הבולס בחירות גבוהות, בהן הם השתמשו כדי לבחור את בן גורדון (בחירה שלישית) ולואול דנג (בחירה שביעית). בנוסף הם בחרו בבחירה ה-38 את כריס דוהון. בנוסף הם החתימו את אנדרס נוצ'יוני שזכה לא מזמן במדליה אולימפית ביחד עם נבחרת ארגנטינה. אחרי שהפסידו בכל 9 המשחקים הראשונים בעונה זו הבולס החלו להראות סימנים של שיפור, בהגנה ובמשחקם ברבע הרביעי. את העונה הם סיימו עם מאזן 35–47, במקום השלישי במזרח והעפילו לפלייאוף לראשונה מאז עונת בה זכו באליפות. הבולס הפסידו בסיבוב הראשון לוושינגטון ויזארדס 4-2. באותה עונה גורדון הפך לרוקי הראשון בהיסטוריה של הליגה שזוכה בתואר השחקן השישי של העונה ב-NBA, והראשון בבולס מאז טוני קוקוץ'.
במהלך קיץ 2005 הבולס החתימו את טייסון צ'נדלר והחזירו אותו לקבוצתם. בכל אופן, זוהו מחלות לב אצל אדי קרי שהיה צריך ללכת לבדיקות DNA. קרי סירב ללכת לבדיקות והועבר לניו יורק ניקס ביחד עם אנטוניו דייוויס בתמורה למייקל סוויטני וטים תומאס. במשך העונה הבולס התקשו לייצר ניצחונות, אך סיום של 2–12 נתן להם מאזן 41-41 והעפלה שנייה ברציפות לפלייאוף. הבולס הפסידו בסיבוב הראשון למיאמי היט 4-2, שבסוף העונה תזכה באליפות.
בדראפט 2006 הבולס בחרו את למרכוס אולדרידג' בבחירה השנייה והעבירו אותו מיד לפורטלנד טרייל בלייזרס בתמורה לטיירוס תומאס וויקטור חריאפה. בנוסף הם בחרו את רודני קארני והעבירו אותו לפילדלפיה 76' בתמורה לתאבו ספולושה. לאחר מכן חתם שחקן ההגנה בן וולאס בקבוצה. אחר כך הם העבירו את טייסון צ'נדלר לניו אורלינס הורנטס בתמורה לפי. ג'יי. בראון וג'יי. אר. סמית'. את עונת סיימו הבולס עם מאזן 33–49, השלישי בטיבו באזור המזרח. בסיבוב הראשון הם נפגשו עם ההיט שהדיחו אותם בשנה שעברה ומנסה להגן על תואר האליפות. הבולס הדהימו את ההיט כשניצחו בסוויפ 0–4, ועברו סיבוב פלייאוף לראשונה מאז עונת 1997/1998 בה שיקגו זכתה באליפות ביחד עם ג'ורדן. בחצי גמר המזרח הם נפגשו עם דטרויט פיסטונס, וזו הפעם הראשונה מאז 1991 שהקבוצות נפגשות בפלייאוף. הפיסטונס ניצחו בשלושת המשחקים הראשונים בסדרה, אך הבולס ניצחו בשני המשחקים הבאים כדי לצמצם את ההובלה ל-2–3. בסוף הפיסטונס ניצחו את הבולס 2–4.
במשך קיץ 2007 החתימו הבולס את ג'ו סמית' ואדריאן גריפין, ובחרו בבחירה התשיעית בדראפט את הסנטר ג'ואקים נואה. הבעיות החלו כשבן גורדון ולואול דנג סירבו להצעות הארכת חוזה ללא סיבות נראות לעין. אחר כך היו שמועות שהבולס הולכים להביא אליהם שחקני אולסטאר כקווין גארנט, פאו גאסול וקובי בראיינט. אף אחת מהעסקאות האלו לא התבצעה. אף על פי שעתידה של הקבוצה נראה טוב, עונת הייתה רחוקה מהציפיות. הבולס החלו את עונת 2007/2008 עם 10 הפסדים מתוך 12 משחקים, ואחרי מאזן 9–16 פוטר המאמן סקיילס וב-27 בדצמבר 2007 מונה במקומו ג'ים בוילן לעמדת המאמן. ב-21 בפברואר 2008 הועברו בן וולאס, ג'ו סמית', אדריאן גריפין ובחירת דראפט לקליבלנד קאבלירס בתמורה לדרו גודן, שאנון בראון, לארי יוז וסדריק סימונס. הבולס סיימו את העונה הזו עם מאזן 33–49, ההפך מהעונה שעברה, ולא העפילו לפלייאוף אחרי שלוש עונות רצופות של העפלות.
אחרי שחוזו של בוילן נגמר הבולס חיפשו מאמן חדש. ב-10 ביוני 2008 פקסון מינה לעמדת המאמן את ויני דל נגרו חסר הניסיון. לבולס היו 1.7% אחוזים בלבד לזכייה בבחירה הראשונה של דראפט 2008, ונגד כל הסיכויים הם זכו בה. בבחירה הזו הם בחרו את דריק רוז. אחר כך הם רכשו את הבחירה ה-36 של פורטלנד טרייל בלייזרס, עומר אשיק. ב-30 ביולי 2008 חתמו הבולס על הארכת חוזה עם לואול דנג למשך שש השנים הבאות בתמורה ל-71 מיליון דולר. דנג היה פצוע ברוב עונת . מאוחר יותר חתם בן גורדון על הארכת חוזה בת שנה אחת. ב-18 בפברואר 2009 ביצעו הבולס טרייד, כששלחו את אנדרס נוצ'יוני, דרו גודן, סדריק סימונס ומייקל ראפין לסקרמנטו קינגס בתמורה לבראד מילר וג'ון סלמונס. יום לאחר מכן, יום מועד ההעברות, הם העבירו את לארי יוז לניקס בתמורה לטים תומאס, ג'רום ג'יימס ואנתוני רוברסון. מאוחר יותר באותו יום הם ביצעו טרייד שלישי בתוך 24 שעות, כשהעבירו את תאבו ספולושה לאוקלהומה סיטי ת'אנדר בתמורה לבחירת דראפט ב-2009. הטריידים עזרו לבולס לסיים את עונת 2008/2009 כמו שצריך, עם מאזן 41-41 ועלייה לפלייאוף. המאזן שלהם הספיק למקום ה-7 במזרח, מה שמסדר להם מפגש קשה בסיבוב הראשון נגד בוסטון סלטיקס המנסה להגן על תואר האליפות משנה שעברה. במשחק הראשון קלע רוז 36 נקודות והוסיף 11 אסיסטים, כשהוא משווה את שיאו של כרים עבדול-ג'באר למספר הנקודות הגבוה ביותר לשחקן שנה ראשונה בהופעת בכורה בפלייאוף. במהלך הסדרה היו 7 הארכות, וזו הסדרה עם מספר ההארכות הרב ביותר בהיסטוריה של הליגה. בסופה של ניצחו הסלטיקס 3–4 והדיחו את הבולס. מומחים רבים טוענים שזו אחת מהסדרות הטובות בהיסטוריה של הליגה.