במהלך מלחמת העולם השנייה וכיבושה של אינדונזיה בידי היפנים, אינדונזים רבים עברו להתגורר במלבורן. במהלך תקופה זו הושמו יהודי אינדונזיה במחנות, והמוסלמים נדרשו להתפלל לכיוון טוקיו ולא מכה. מצידה של אוסטרליה, חיילים מטעמה לקחו חלק בקרב בורנאו נגד היפנים. ב-17 באוגוסט 1945, פחות מחודש לפני כניעתה של יפן, הכריז סוקרנו, שהנהיג את המושבה, על עצמאות המדינה. לאחר ההכרזה נדרשו עוד ארבע שנים של מלחמת גרילה נגד ההולנדים והיפנים בטרם הוכרה עצמאותה של אינדונזיה.
עצמאות אינדונזיה.
על אף האהדה בקרב חלקים מהשמאל האוסטרלי למפלגה השלטת באינדונזיה, אוסטרליה לא הכירה באינדונזיה דה פקטו אלא ב-9 ביולי 1947 באופן חלקי. מספר ימים לאחר מכן, ב-20 ביולי, ובעקבות כישלון המגעים בין תומכי העצמאות להולנד, פתחה האחרונה בהתקפה צבאית באיים ג'אווה וסומטרה. מהזווית האוסטרלית, שלושה שבועות לפני ההכרה האוסטרלית בעצמאות אינדונזיה ועד ההכרה ההולנדית, פועלים אוסטרלים בנמלים החרימו את הספינות ההולנדיות ששטו מאוסטרליה לאינדונזיה, במה שכונה בהמשך "הארמדה השחורה".
אוסטרליה הביעה את עמדתה על הסכסוך בין הולנד לאינדונזיה בדיון במועצת הביטחון של האו"ם ב-30 ביולי 1947, כשהאשימה את הולנד בהפרת השלום. אוסטרליה המשיכה והעלתה את הנושא לסדר היום של המועצה. יומיים מאוחר יותר, הוחלט באו"ם על הפסקת אש ועל הקמת ועדה לחידוש השיחות. ההנהגה האינדונזית הציגה את אוסטרליה כמועמדתה לחברה בוועדה, שהביאה בסופו של דבר להסכם רנוויל בינואר 1948. ההסכם לא החזיק מעמד זמן רב, ובדצמבר 1948 פתחו ההולנדים בהתקפה חדשה (מבצע עורב) על הכוחות האינדונזיים והצליחו לכבוש שטחים באי ג'אווה. המצב בשטח בין הצדדים הביא לייסוד שולחן עגול מאוגוסט ועד נובמבר 1949 ובדצמבר 1949 הולנד הכירה בעצמאות אינדונזיה. בתגובה לכך אוסטרליה הייתה לראשונות במדינות העולם שהכירו ברפובליקה החדשה.
לאחר מתן העצמאות שתי המדינות העניקו אחת לשנייה מעמד מדינה מועדפת, כשב-1959 נחתם הסכם בנושאי מסחר ומכסים. המעמד ההדדי נמשך עד היום, למעט בשנים 1970-1972.
תקופת סוקארנו.
ממשלת אוסטרליה בתקופתו של רוברט מנזיס לא אהדה את ההתקרבות בין סוקארנו לבין המפלגה האינדונזית הקומוניסטית, דבר שנמשך עד 1965. למרות זאת, מנזיס היה לראש הממשלה האוסטרלי הראשון שביקר באינדונזיה.
ב-1961, סוקארנו, בתמיכתה של המפלגה הקומוניסטית סיפח את פפואה המערבית, על רקע הידיעות על העצמאות שההולנדים תכננו להעניק למחוז. השטח הועבר סופית לשליטתה של אינדונזיה ב-1963, ו"מעשה הבחירה החופשית" הושלם ב-1969.
אוסטרליה סייעה למלזיה בתקריות בינה לבין אינדונזיה בין אפריל 1964 עד אוגוסט 1966. הכוחות האוסטרליים בסראוואק הוצבו פעמים רבות מעבר לגבול וארבו לסיורים אינדונזים באותן שנים. עם זאת, שר החוץ האוסטרלי, גרפילד בארווקי נמנע מעימות ישיר מול אינדונזיה, והגדיר את המעורבות האוסטרלית כ"תגובה מדורגת ומוקפדת" לבקשות הבריטיות והמלאיות. במהלך השנתיים הללו נהרגו 23 אוסטרלים, שבעה מהם במהלך פעילות מבצעית, ושמונה נוספים נפצעו.
תקופת סוהארטו.
עמדתו של סוהארטו נגד הקומוניזם תאמה את עמדותיהן של ממשלות אוסטרליה לאורך השנים. שר החוץ של אוסטרליה, פול הזלק, הספיק לבקר בין השנים 1966–1968 שלוש פעמים באינדונזיה לפני שסוהארטו נבחר באופן רשמי לנשיא, דבר המצביע על היחסים הטובים בין הצדדים באותן שנים. ביוני 1968 ביקר באינדונזיה ראש ממשלת אוסטרליה, ג'ון גורטון ב-1972 סוהארטו ביקר באוסטרליה ונפגש עם ראש הממשלה ויליאם מקמהון. ב-1974 ביקר שוב ראש ממשלת אוסטרליה, גוף ויטלם באינדונזיה ונפגש עם סוהארטו. הביקור האחרון של סוהארטו באוסטרליה התקיים ב-1975.
לאורך השנים שתי המדינות חתמו על כמה הסכמים, הראשון שבהם הוא הסכם לשיתוף פעולה תרבותי, חינוכי, אומנותי וספורטיבי והוא נחתם ב-1968. ב-1973 אוסטרליה תרמה מיליון דולר לשיקום ושימור הבורובודור, מונומנט מהאיאני בודהיסטי שבאינדונזיה. באותה שנה המשא ומתן על הגבול בין שני הצדדים בים אראפורה הסתיים.
במהלך הפלישה האינדונזית לטימור הפורטוגזית ב-1975 נהרגו חמישה עיתונאים אוסטרלים. בתחקיר מ-2007 התגלה כי העיתונאים נהרגו בכוונת מכוון על ידי חיילים של הכוחות האינדונזים. לפי אינדונזיה, העיתונאים נהרגו במהלך חילופי אש בין הכוחות לבין מיליציה של תומכי העצמאות. לאורך הפלישה ממשלת אוסטרליה פעלה כדי למנוע מעורבות כלשהי בסכסוך ואף עודדה את אינדונזיה לכבוש את המקום מחשש להשתלטות של השמאל על המושבה לשעבר. בשנים שאחרי הפלישה ועד עזיבת האינדונזים, בין רבע לשליש מהאוכלוסייה נהרגה, כ-200 אלף בני אדם. ב-1976 ראש ממשלת אוסטרליה מלקולם פרייזר נפגש עם סוהארטו. ב-1978 אוסטרליה הודיעה על הכרה דה פקטו בסיפוח האינדונזי של מזרח טימור, וב-1979 על הכרה דה יורה, ובכך הייתה למדינה היחידה שהכירה באופן מלא במהלך.
הסכם האזור המשותף של טימור נחתם בדצמבר 1989 ועסק בייסוד אזור לשיתוף פעולה במים בין טימור לאוסטרליה. האזור עשיר בנפט וגז, וההסכם נועד לפתור את המחלוקות בין שתי המדינות בנוגע לבעלות על המקום. הסכם הגבול הימי קבע את הגבול הסופי בין שתי המדינות ונחתם ב-1997.
ב-1992 הושג הסכם למניעת כפל מס ותכנון מס. בשנים אלו ביקר באינדונזיה מספר פעמים ראש ממשלת אוסטרליה פול קיטינג ונועד עם סוהארטו. בכהונת ממשלתו של קיטינג נערך פורום השרים הראשון ב-1994.
בתקופת המשבר הפיננסי באסיה, אוסטרליה העבירה 8.8 מיליון דולר כדי לפתור בעיות באינדונזיה שנגרמו בגלל הבצורת, עליית מחירי המזון והאבטלה, בעיות שהיו בולטות במזרח אינדונזיה. אוסטרליה גם התירה לאינדונזיה ללוות מיליארד דולר כסיוע נוסף לייצוב המטבע האינדונזי.
מזרח טימור.
היחסים בין שתי המדינות הגיעו לשפל בעת המאבק של מזרח טימור לעצמאות ב-1999. באותה שנה הושג הסכם בין האו"ם לבין אינדונזיה, ובו נקבע כי תושבי מזרח טימור יוכלו לבחור בין אוטונומיה בשלטון אינדונזי לבין עצמאות מלאה, ובמשאל העם ניצחו תומכי העצמאות. אחרי המשאל, כוח המשימה האוסטרלי-אינדונזי INTERFET נשלח למקום כדי לשמור על הסדר לאחר שכוחות פרו-אינדונזים הפרו אותו בתמיכת הצבא האינדונזי.
בתגובה למעורבות האוסטרלית, אינדונזיה ביטלה את הברית הביטחונית בין המדינות שנחתמה ב-1995 בטענה כי הפעולות האוסטרליות אינן עולות בקנה אחד עם רוח ההסכם. מפגשים רשמיים וועידות עוכבו או בוטלו, ופורום השרים לא התקיים עד מרץ 2003. זמן מה אחר כך הוחלף הכוח האוסטרלי בכוח בינלאומי, UNTAET.
המלחמה בטרור.
היחסים בין המדינות הפכו למתוחים בעקבות פרשת טמפה כשבאוגוסט 2001 אוסטרליה סירבה לאשר את כניסתה של אוניית המשא הנורווגית טמפה (MV Tampa) שנשאה על סיפונה מבקשי מקלט אפגנים שחולצו מסירה במים בינלאומיים. האינדונזים וסוכנות ההצלה (Rescue Agency) לא הגיבו במהירות לבקשות האוסטרליות לקבל את הנוסעים. אחרי שהספינה נכנסה ללא היתר למימיה של אוסטרליה, זו עשתה מאמץ לשכנע את האינדונזים לקבל את מבקשי המקלט, כשגם נורווגיה סירבה לקבלם ודיווחה על אוסטרליה לסוכנויות בינלאומיות. המשבר גרם לאוסטרליה ולאינדונזיה לשתף פעולה באופן הדוק יותר במה שקשור להגירה, ולאחר מכן נערכו ועידות אזוריות שנוגעות להברחות וסחר בבני אדם.
בשנת 2002 בוצעה מתקפת טרור בקוטה, באלי במהלכה נרצחו 202 בני אדם, מתוכם 88 אוסטרלים, ונפצעו 240 נוספים. ארגון אל-ג'מאעה אל-אסלאמיה נטל את האחריות על הפיגוע, וטען שהוא בוצע בתגובה לתמיכה של אוסטרליה בעצמאות מזרח טימור. פיגוע נוסף התרחש ב-2005, והביא למותם של 25 אנשים, מתוכם 15 אינדונזים ו-4 אוסטרלים, וכן נפצעו 101 בני אדם.
פיגוע אחר שהתרחש באינדונזיה ב-2003 כוון גם כן נגד מטרות מערביות, כשארגון אל-קאעדה טען שהוא בוצע בידי אל-ג'מאעה אל-אסלאמיה בתגובה לפעולותיהן של ארצות הברית ובנות בריתה, ביניהן אוסטרליה. בשנת 2004 הותקפה השגרירות האוסטרלית בג'קרטה, גם כן בידי הארגון, מתקפה שגרמה למותם של תשעה אזרחים אינדונזים. שנה אחר כך, עובדי השגרירות והקונסוליה האינדונזית באוסטרליה קיבלו מעטפות שהכילו איומים. מאז, ארצות הברית ואוסטרליה הוציאו אזהרת מסע לאינדונזיה והזהירו מפני פיגועים נוספים.
האירועים שהתרחשו באינדונזיה ובאוסטרליה הביאו את שתי המדינות לשתף פעולה באופן הדוק יותר בין רשויות אכיפת החוק, בהתבסס על הסכם שנחתם ב-1999 ונגע להעברת סמים והלבנת הון. צוות שיתוף הפעולה האזורי של המשטרה האוסטרלית בג'קרטה סייע למשטרה האינדונזית ותרם למרכז ג'קרטה לשיתוף פעולה באכיפת החוק. הפעילות הזו משכה ביקורת, במיוחד אחרי שנעצרו בבאלי 9 אוסטרלים בחשד שניסו להבריח הרואין לאוסטרליה.
בעקבות הצונאמי ב-2004, אוסטרליה סיפקה סיוע הומניטרי שכלל חבילת סיוע בשווי מיליארד דולר מהממשלה הפדרלית, תרומה של 17.45 מיליון דולר ממדינות אוסטרליה ופרסום התחייבות של 900 אנשי צבא אוסטרלים להצטרף לסיוע בצפון סומטרה ואצ'ה. בנוסף לסיוע הממשלתי, ערכו שלושת ערוצי הטלוויזיה המובילים באוסטרליה משדר מיוחד שנקרא "אוסטרליה מתאחדת: הושיטו יד לאסיה" שגייס תרומות בשווי 10 מיליון דולר, ובסך הכל תרומה פרטית של 140 מיליון דולר.
הגירה.