Το Υπουργείο Άμυνας της Αυστραλίας ανακοίνωσε ότι σκοπεύει, στο πλαίσιο του προγράμματος «Project AIR 7404 Phase-1», να αντικαταστήσει τα 12 εν υπηρεσία μεταφορικά αεροσκάφη C-130J Super Hercules, με τον ίδιο τύπο αεροσκάφους, αλλά σε μεγαλύτερο αριθμό. To 1995 η Αυστραλία προχώρησε στην προμήθεια 12 C-130J, τα οποία άρχισε να παραλαμβάνει το 1999. Μέχρι το 2012 τα αεροσκάφη είχαν εφοδιαστεί με σύστημα προειδοποίησης εντοπισμού από ραντάρ, ενώ μέχρι το 2015 τα αεροσκάφη είχαν αποκτήσει συστήματα δορυφορικών επικοινωνιών, ικανότητα Link-16 και νέα οπίσθια ράμπα. Επίσης, αναβαθμίστηκε το λογισμικό τους. Τέλος, στις αρχές του 2020 ξεκίνησαν δοκιμές πιστοποίησης και χρήσης, από τα αεροσκάφη του ατρακτιδίου Litening.
Το 2020 το Υπουργείο Άμυνας της Αυστραλίας εξέδωσε το έγγραφο «Force Structure Plan», σύμφωνα με το οποίο υπάρχει ανάγκη αντικατάστασης των C-130J και αύξησης του αριθμού των μεταφορικών αεροσκαφών. Το 2001 η Αυστραλία έστειλε επιστολή ενδιαφέροντος στη Lockheed Martin για πιθανή προμήθεια 24 νέων C-130J-30 και έξι (6) αεροσκαφών εναέριου ανεφοδιασμού KC-130J. Ανάλογες επιστολές στάλθηκαν στην Airbus, την Embraer και την Kawasaki, αλλά τελικά προτιμήθηκε το C-130J-30. Ο προϋπολογισμός του προγράμματος «Project AIR 7404 Phase-1» είναι $ 9-14 δισεκατομμύρια και η υλοποίηση του αναμένεται να εγκριθεί από την κυβέρνηση εντός του 2023. Σύμφωνα με αυστραλιανά μέσα ενημέρωσης η προμήθεια των 30 C-130J-30 και KC-130J μπορεί να σημάνει την απόσυρση/αντικατάσταση και των 10 εν υπηρεσία C-27J Spartan, χωρίς όμως να υπάρχει επίσημη επιβεβαίωση/διάψευση για κάτι τέτοιο.
Σύμφωνα με τον προγραμματισμό, το πρώτο C-130J-30 αναμένεται να παραδοθεί στην Αυστραλία το 2030, όταν τα εν υπηρεσία C-130J θα είναι περίπου 30 ετών. Ο λόγος για τον οποίο η Αυστραλία δεν επιλέγει την αναβάθμιση των υφιστάμενος αεροσκαφών είναι διότι η χώρα ήταν από τις πρώτες που παρέλαβαν αεροσκάφη του τύπου, τα οποία είναι της αρχικής έκδοσης, και σήμερα παράγονται αεροσκάφη με πιο σύγχρονα συστήματα (ηλεκτρονικά, πλοήγησης, αυτοπροστασίας και διαχείρισης φορτίου). Ένας άλλος λόγος είναι η εκτεταμένη τους χρήση, άρα η «κατανάλωση» των επιτρεπόμενων ωρών πτήσης των αεροσκαφών. Προφανώς κρίθηκε ότι ένα πρόγραμμα αναβάθμισης και επέκτασης της επιχειρησιακής τους ζωής θα ήταν ασύμφορο και ότι η προμήθεια νέων αεροσκαφών είναι η βέλτιστη λύση.
