הקבוצה החלה את דרכה בשנת 1939 בשם סירקיוז רדס, ומוקמה בסירקיוז, ניו יורק. עד שנת 1941 הרדס שיחקו רק נגד קבוצות מקומיות כמו ניו יורק רנסאנס, ניו יורק ג'ולס ואוסווגו מרצ'נטס. כמה מהשחקנים הבולטים של הרדס בשנים אלו היו ווילמת' סידאת-סין, מארק הלר ואל סרבי (שהגיע להיכל התהילה). בשנים 1942–1945 עדיין לא שיחקה הקבוצה בליגה מקצוענית.
לפני עונת 1946/1947 הצטרפו הרדס לליגת ה-NBL, ושינו את שמם ל"סירקיוז נשיונלס". בעונה זו השיגו הנשיונלס מאזן 21–23 וסיימו במקום הרביעי. בפלייאוף הנשיונלס הודחו בידי רוצ'סטר רויאלס בסדרה בת ארבעה משחקים. בעונתם השנייה הנשיונלס הצליחו פחות, כשהשיגו מאן 24–36 וסיימו במקום ה-5 את העונה. הם הגיעו לפלייאוף והודחו על ידי האנדרסון דאפי פאקרס בסדרה בת 3 משחקים.
לפני עונת 1947/1948 כמה קבוצות עזבו את ה-NBL לליגת ה-BAA, כשהייתה הנחה שהם יתאחדו בקרוב. הנשיונלס החתימו את אל סרבי ודולף שייס היהודי, שבעתיד יהיה גם מאמן הקבוצה. את עונה זו הנשיונלס סיימו במאזן 23–40, הפעם הראשונה שלהם עם מאזן חיובי. הנשיונלס עברו לראשונה בהיסטוריה שלהם את הסיבוב הראשון של הפלייאוף כשנצחו בסדרה 0–2 נגד ההאמונד קלומט באקנירס. למרות זאת בסיבוב השני הנשיונלס הפסידו לאנדרסון דאפי פאקרס בחצי הגמר בסדרה בת 4 משחקים.
1949-1963: הנשיונלס ב-NBA.
בסיום עונת 1947/1948 כל הקבוצות עברו לליגת ה-BAA, שהתאחדה עם ליגת ה-NBL ונוצרה ליגת ה-NBA. עונתם הראשונה של הנשיונלס ב-NBA הייתה הצלחה מיידית, כשהם השיגו מאזן 13–51. בסיבוב הראשון של הפלייאוף הם הדיחו את פילדלפיה ווריורס בסדרה 0–2. בגמר המזרח הנשיונלס נפגשו עם ניו יורק ניקס, וניצחו בדרבי של ניו יורק בסדרה בת 3 משחקים. בגמר הנשיונלס נפגשו עם מיניאפוליס לייקרס. הנשיונלס הפסידו במשחק הראשון בביתם, ולא התאוששו מאז. הם הפסידו בסדרה 1–3.
אף על פי שבתחילת עונת מספר קבוצות עברו לליגת ה-NPBL (National Professional Basketball League) הנשיונלס החליטו להישאר ב-NBA. בעונתם השנייה בליגה הם שיחקו ביכולת בינונית, והשיגו מאזן 32–34. הם סיימו את העונה במקום הרביעי בליגה. בפלייאוף הם נצחו בסיבוב הראשון נגד פילדלפיה ווריורס 0–2. למרות זאת בגמר המזרח הם הפסידו לניקס בסדרה בת 5 משחקים (2–3), כשבמשחק האחרון הם הפסידו ב-2 נקודות בלבד.
אל סרבי הפך לשחקן-מאמן בעונה ההבאה בנשיונלס, כשהוא מכניס שיטה התקפית במיוחד עם הגנה חלשה. התצוגה ההתקפית גרמה לכך שהנשיולנס יובילו את הליגה בנקודות בממוצע למשחק, עם 79.5. הם סיימו את העונה עם מאזן 26–40. בסיבוב הראשון של הפלייאוף הנשיונלס נצחו בפעם השלישית ברציפות את פילדלפיה ווריורס בסדרה בת 3 משחקים. למרות זאת, הנשיונלס הפסידו בגמר המזרח לניקס בפעם השנייה ברציפות בסדרה בת 4 משחקים.
בעונת הנשיונלס סיימו במקום השני בליגה, כשהיה קרב קשה מצד עוד שתי קבוצות באזור המזרח. הם השיגו מאזן 24–47. בסיבוב הראשון הם פגשו את בוסטון סלטיקס והפסידו במשחק הראשון 81–87 בביתם. כשהם רצו להשאיר לעצמם סיכוי הם היו צריכים לנצח במשחק השני. המשחק הזה הפך לאחד המשחקים הארוכים ביותר בהיסטוריה של ה-NBA, והארוך ביותר בפלייאוף בכל הזמנים. הוא כלל ארבע הארכות, ובסופו הנשיונלס הפסידו 105–111 לסלטיקס.
הנשיונלס רכשו את אלכס גרוזה וראלף בירד מאינדיאנפוליס אולימפיאנס שעזבה את הליגה, והשאירה אותה עם 9 קבוצות בלבד. את עונת הם סיימו עם מאזן 30–42. הנשיונלס עברו את סיבוב הפלייאוף הראשון בקלות, ונשארו במומנטום כשנצחו את הסלטיקס בגמר המזרח בסדרה בת 2 משחקים. בגמר הם פגשו את הלייקרס, והפסידו בסדרה קשה וצמודה בת 7 משחקים.
ליגת ה-NBA התחילה להתמודד עם קשיים כספיים, ועוד קבוצה עזבה אותה והשאירה אותה עם 8 בלבד. לנוכח אי הפופולריות של הליגה מנהל הנשיונלס, דני ביאסון, הגיע עם הצעה לליגה. הוא הציע שכל התקפה של קבוצה תארוך 24 שניות בלבד (החוק שעומד עד היום) ולא 30, שיאפשר למשחקים להתנהל בצורה מהירה יותר. שעון ה-24 הפך להצלחה מיידית, כשקצב הנקודות עלה ב-14 בממוצע מהעונה הקודמת. בעונת הנשיונלס סיימו עם מאזן 29–43, וסיימו במקום הראשון במזרח.
הנשיונלס עברו את סיבוב הפלייאוף הראשון, ובגמר המזרח הם ניצחו את בוסטון סלטיקס בסדרה בת 4 משחקים ועלו לגמר NBA שני ברציפות. בגמר הם נפגשו עם הפורט ווין פיסטונס. בשני המשחקים הראשונים בביתם הנשיונלס ניצחו. בשלושת המשחקים ההבאים בפורט ווין הפיסטונס לקחו את כולם, ועלו למאזן 2–3 בסדרה. במשחק ה-6 בסירקיוז הנשיונלס ניצחו 104–109, וכפו משחק שביעי ומכריע. במשחק השביעי זריקת עונשין של ג'ורג' קינג נתנה לנשיונלס יתרון 91–92 שניות לפני סיום המשחק. במהלך הבא קינג חטף את הכדור מהוצאת החוץ של הפיסטונס, וסיים את המשחק בניצחון הנשיונלס. זו הייתה אליפות ה-NBA הראשונה של הנשיונלס בהיסטוריה של המועדון.
אחרי עונת האליפות התרחשה ירידת מתח בנשיונלס, שסיימו את עונת במאזן 35–37, וכמעט במקום האחרון בליגה. למרות היכולת החלשה בעונה הסדירה הנשיונלס הפתיעו את הסלטיקס בסיבוב הראשון של הפלייאוף כשנצחו 1–2. בגמר המזרח הם שחקו נגד פילדלפיה ווריורס, והפסידו בסדרה בת 5 משחקים.
אחרי כמה משחקים בלבד בעונת פוטר סרבי ובמקומו מונה לעמדת המאמן פול סימור. ביחד עם סימור הנשיונלס חזרו ליכולתם הטובה וסיימו את העונה במקום השני במזרח עם מאזן 34–38. בסיבוב הפלייאוף הראשון הנשיונלס נפגשו עם האלופה הנוכחית, פילדלפיה ווריורס, והדיחה אותה עם 0–2 בסדרה אחרי שני משחקים צמודים. למרות זאת הנטס יודחו בסוויפ בסיבוב הבא על ידי הבוסטון סלטיקס.
פורט ווין פיסטונס עברו לדטרויט (ושונה שמם לדטרויט פיסטונס) ורוצ'סטר רויאלס עברו לסינסינטי (ושונה שמם לסינסינטי רויאלס), ובכך הם השאירו את הנשיונלס כקבוצה האחרונה ב-NBA שבמגיעה מעיר קטנה כמו סירקיוז. על המגרש זה לא שינה והנשיונלס סיימו במקום השני במזרח עם מאזן 31–41. למרות זאת, הם הפסידו בסיבוב הראשון של הפלייאוף לפילדלפיה ווריורס.
אף על פי שהנשיונלס סיימו את עונת עם מאזן 35–37 הם עלו לפלייאוף מהמקום ה-3 במזרח. בסיבוב הראשון הם הדיחו בסוויפ את ניו יורק ניקס, והם עלו לגמר המזרח. בגמר המזרח הם התמודדו מול בוסטון סלטיקס. הם הצליחו למשוך את המשחק עד למשחק השביעי המכריע, בו הם הפסידו ב-5 נקודות הפרש והפסידו בסדרה 3–4 לסלטיקס.
עונת התאפיינה בעיקר בחוזקתן של הקבוצות עם הסופרסטארים כמו ביל ראסל של הסלטיקס, וילט צ'מברלין של הווריורס ובוב פטיט של הסנט לואיס הוקס. למרות זאת הנשיונלס השיגו מאזן טוב של 30–45 בסיום העונה, ומקום 3 במזרח. בסיבוב הראשון של הפלייאוף הם הפסידו לווריורס וצ'מברלין בסדרה בת 3 משחקים.
כשהלייקרס עברו ממיניאפוליס ללוס אנג'לס הנשיונלס נשארו קבוצת ה-NBL היחידה שנשארה באותו מקום מאז המעבר ל-NBA. הם סיימו במקום השלישי במזרח עם מאזן 38–41. בסיבוב הראשון הנשיונלס הדהימו את פילדלפיה ווריורס כשהדיחו אותם בסוויפ בסדרה בת 3 משחקים. למרות זאת, בגמר המזרח הם הפסידו לסלטיקס בסדרה בת 5 משחקים.
בעונת דולף שייס פיספס 24 משחקים, ולראשונה מזה 14 שנים הוא לא הוביל את קבוצתו בנקודות בממוצע למשחק. אותו החליף האל גריר שקלע 22.8 נקודות בממוצע למשחק. הנטס סיימו את העונה במקום ה-3 במזרח עם מאזן 39–41. בסיבוב הראשון הם פגשו את הווריורס. לאחר שהפסידו בשני המשחקים הראשונים בחוץ ועמדו בפני הדחה הם ניצחו בשני משחקי הבית שלהם וכפו משחק חמישי ומכריע. במשחק החמישי הווריורס ניצחו 104–121 והנשיונלס הודחו. בסיום אותה עונה הווריורס עברו מפילדלפיה לסן פרנסיסקו. מהלך זה גרם שלעיר פילדלפיה לא תהיה קבוצת כדורסל, ובעתיד הנשיונלס יתפסו את המקום הזה.
בתחילת עונת הציפיות היו שהנשיונלס יתחילו בתהליך דעיכה מכיוון שהסגל שלהם מתחיל להזדקן. למרות זאת הם נשארו בתמונת האליפות כשסיימו את העונה במקום השני בליגה עם מאזן 32–48. בסיבוב הראשון של הפלייאוף הם פגשו את סינסינטי רויאלס. בתחילה הם הובילו 1–2. אף על פי שהם היו צריכים ניצחון אחד בשביל להעפיל לסיבוב הבא הם הפסידו בשני המשחקים ההבאים והודחו. ההפסד האחרון לרויאלס 127–131 הפך למעשה למשחק האחרון של הקבוצה בסירקיוז.
1963-1968: המעבר לפילדלפיה ועידן וילט צ'מברלין.
בשנת 1963 הנשיונלס ביצעו את המעבר לפילדלפיה, אחרי שנשארו הקבוצה היחידה שמוצאה בעיר קטנה. המעבר התאפשר מפני שקודם לכן הפילדלפיה ווריורס עברו לסן פרנסיסקו. בנוסף קשיים כלכליים הכריחו את המעבר. לאחר המעבר לפילדלפיה נערכה תחרות לבחירת כינוי לקבוצה. בסופה נבחר הכינוי 76ers ("סֶבֶנְטִי-סִיקְסֶרְס"), קיצור לשנת 1776 שהיא שנת הכרזת העצמאות של ארצות הברית שהתרחשה בפילדלפיה. מאז הם נקראו פילדלפיה 76'.
אחרי המעבר דולף שייס מונה לעמדת המאמן, לאחר ששיחק קודם לכן במדי הקבוצה. את העונה הראשונה בפילדלפיה הם סיימו עם מאזן 34–46 ועלו לפלייאוף. הם הפסידו בחצי גמר המזרח 2–3 לסינסינטי קינגס. לפני עונת 1964/1965 פילדלפיה רכשה את האולסטאר וילט צ'מברלין מהווריורס.