מאז 1935 שכנה מפקדת הלשכה בבניין משרד המשפטים של ארצות הברית, שלו היא כפופה. הצעה להקים בניין מפקדה נפרד עבורה הועלתה כבר בשנת 1939, אך מלחמת העולם השנייה הביאה לדחיית מימוש הרעיון, והבנייה אושרה על ידי הקונגרס רק ב-1962. בניית הבניין החלה ב-1967 והוא נחנך על ידי הנשיאפורד ב-30 בספטמבר1975. הוא אוכלס בהדרגה בשנים 1974–1977. ב-4 במאי1972, יומיים לאחר פטירתו של ג'יי אדגר הובר ובעוד הבניין עומד בבניינו, החליט הקונגרס בחוק לקרוא לבניין על שמו.
תכנונו של הבניין, שנעשה בסגנון האדריכלי הברוטליסטי, ספג ביקורת. קירותיו החיצוניים עשויים כולם בטון יצוק (נטען שהדבר נעשה מטעמי חיסכון).[1] גובה הבניין בחלקיו השונים מגיע לשבע עד 11 קומות. על פי תוכניותיו משתרע שטח רצפותיו על פני 260,200 מטרים מרובעים והוא מיועד לאכלס 7,090 עובדים. אדריכלי הבניין היו משרד צ'ארלס פ. מרפי (Charles F. Murphy) בשיתוף עם סטניסלב ז. גלדיץ (Stanislaw Z. Gladych). עלות בנייתו הגיעה ל-126.1 מיליון דולר.
בחצר הבניין ניצבת אנדרטה לג'יי אדגר הובר, שהוקמה ביזמת אגודת סוכני הלשכה לשעבר. האנדרטה, שנחנכה בשנת 1979, נושאת את השם נאמנות, גבורה, יושרה (שהוא המוטו של הלשכה). היא עשויה ארד וכוללת שלוש דמויות אדם המייצגות את שלושת הערכים שעל שמם היא קרויה על רקע דגל ארצות הברית הנראה כמתנופף ברוח. האנדרטה עוצבה על ידי פרדריק צ'ארלס שראדי (Frederick Charles Shrady).
