Newcastle Jets

El primer equipo de fútbol de Newcastle fue el Newcastle KB United, fundado en 1978, un año antes de la formación de la NSL.

La plaza del KB United en la liga fue dada al Adamstown Rosebuds en 1984, luego del colapso del Newcastle KB United. El Rosebuds posteriormente fue renombrado como Newcastle Rosebud United para competir en la NSL.

Newcastle Breakers

La plaza del Rosebuds posteriormente le fue entregada en 1991 al Newcastle Breakers, club formado desde el Newcastle Australs, club de la liga estatal de Nueva Gales del Sur. El Australs fue creado en 1952 por trabajadores de Gretna Austral. El club se había unido a la liga estatal de NGS en 1988. Los colores originales del Australs eran el violeta y blanco

Newcastle United

El Newcastle United fue fundado en 2000 por Con Constantine desde el Breakers,​ que ya estaba casi extinto debido a que se disolvió a finales de la temporada 1999/00 luego de que Soccer Australia (actual FFA) acabó con la National Soccer League. Con la creación del Newcastle United el equipo cambió su sede de vuelta al antiguo campo del KB United, ahora conocido como el EnergyAustralia Stadium.

Newcastle United Jets

El Newcastle United fue rebautizado como Newcastle United Jets para la temporada inaugural de la A-League (2005/06) para proyectar una nueva imagen y evitar confusiones con el club de la FA Premier League, el Newcastle United F.C..

El nombre Jets es una referencia a la base Williamtown de la Real Fuerza Aérea Australiana, ubicada 20 kilómetros al norte de Newcastle. El escudo del club muestra tres F/A-18 Hornet, en referencia a las aeronaves que la RAAF tiene en Williamtown.

A-League

El exentrenador de las selecciones de Inglaterra y Australia, Terry Venables, había sido tentado para dirigir a los Jets en su primera temporada en la A-League, pero la noticia fue descartada por el agente de Venables,​ por lo que Richard Money fue designado como entrenador del equipo para la temporada 2005/06. En 2006, Money fue reemplazado por Nick Theodorakopoulos luego que el primero volviera a Inglaterra para dirigir al Walsall. En octubre de 2006, luego de no conseguir triunfos ni en la Copa de Pretemporada ni en las siete primeras fechas de la A-League, Theodorakopoulos fue el primer entrenador despedido en la historia del club en la A-League. Su asistente, Gary van Egmond, fue nombrado técnico interino por el resto de la temporada, aunque recientemente firmó un contrato de tres años.

El club sorprendió a todos los espectadores de la liga al fichar a Ned Zelic,​ jugador que había roto sus lazos con Australia al haber renunciado a la selección nacional.

Tiempo después, algunos reportes anunciaban que el club estaba tentando al exdelantero del Liverpool y la selección de Inglaterra, Stan Collymore, a salir de su retiro y fichar por el club.​ El director deportivo de la institución, Remo Nogarotto, confirmó que los Jets le habían ofrecido a Collymore que juegue con los Jets cuatro partidos de la A-League, aunque la idea se descartó solo 24 horas después de hacerla pública.​

El 19 de enero de 2007 los Jets finalizaron en el tercer puesto de la fase final de la A-League tras caer por 4-0 ante los premieres y a la postre campeones, Melbourne Victory.

Bajo la dirección de Gary van Egmond el equipo consiguió la mayor cantidad de puntos posibles en 14 fechas de todos los equipos de la liga, además de marcar una gran cantidad de goles. Esto trajo como resultado que multitudes fueran al estadio de los Jets para ver los partidos, llegando a un público récord de más de 24.000 personas en el último cotejo de la fase regular entre el Newcastle United Jets y el Sydney FC el 2 de febrero de 2007

En la liguilla final el Newcastle fue eliminado por el Adelaide United en definición por penaltis luego de empatar el partido a 1 gol. Vaughan Coveny y Stuart Musialik erraron sus tiros para dejar el marcador 4-3 en favor de Adelaida, costándole a Newcastle el pase a la final y un cupo en la Liga de Campeones de la AFC.

Temporada 2007/2008

La tercera temporada de la A-League vio cómo jugadores de los Jets dejaban el club: Paul Okon, el capitán del equipo, dejaba la actividad; Milton Rodríguez, el favorito de los hinchas, regresaba a su país natal (Colombia) y Nick Carle era vendido al Gençlerbirliği S.K. de Turquía. Las nuevas contrataciones incluyeron al hermano de Joel Griffiths, Adam, y al ex ganador de la Bota de Oro europea, Mário Jardel. Pese a las expectativas surgidas tras la llegada del brasileño, este no fue titular y jugó muy pocos minutos. A lo largo de la temporada la titularidad fue para Joel Griffiths, quién rompió el récord de anotaciones marcando 12 goles en los 21 partidos de la temporada regular.​

La temporada comenzó muy bien para los Jets, que estuvieron invictos en sus primeros cinco partidos. Después de este inicio de torneo, los Jets tuvieron una campaña irregular, en la cual ganaban muchos partidos, aunque también perdían partidos de importancia vital. Ya en la recta final del campeonato, tuvieron una reñida lucha con los Central Coast Mariners, los cuales finalizaron primeros por diferencia de goles. Estos dos equipos se enfrentaron en las semifinales, ganando los Jets el partido de ida con goles de Adam Griffiths y de su hermano Joel, este último de penal. El encuentro generó una gran controversia debido a un gol legítimo que se le fue anulado a John Aloisi, sumado al penal que este erró.​

En el partido de vuelta, los Mariners vencieron por el mismo marcador con goles de Sasho Petrovski y Adam Kwasnik, forzando el tiempo suplementario. A los siete minutos del mismo, Petrovski convirtió el gol que llevaba a los Mariners a su segunda final de la A-League en tres temporadas.​

Tras caer en la semifinal, los Jets tuvieron que jugar la final preliminar ante el Queensland Roar para definir al rival de los Mariners en la gran final. Los Jets vencieron al Roar por 3-2 en el tiempo suplementario, accediendo así a su primera gran final en la A-League.​ Los Jets ganaban por 1-0 con gol de Matt Thompson hasta que minutos antes del final del partido una falta en el área de Newcastle provocó un penal que fue convertido por Reinaldo, enviando el partido al tiempo extra. Ya en la prórroga una falta penal sobre Song Jin-Hyung fue cobrada por Joel Griffiths en el minuto 104 para poner a los Jets con un pie en la gran final. En el minuto 111 Tarek Elrich desató la fiesta al convertir el tanto que le daba el 3-1 a Newcastle a falta de sólo 9 minutos para el final. Los jugadores de Queensland intentaron reaccionar consiguiendo una falta penal que nuevamente convertiría Reinaldo, aunque no serviría ya que los Jets se clasificarían de todos modos a su primera gran final.

Finalmente el Newcastle United Jets se coronó campeón de la A-League al derrotar por 1-0 a su verdugo en la semifinal, el Central Coast Mariners, con solitario gol de Mark Bridge en el minuto 64.​ El partido no estuvo exento de polémica, ya que en los minutos finales del encuentro el portero de los Mariners, Danny Vukovic, fue expulsado, quedando así suspendido durante las primeras fechas del siguiente campeonato.​ Pese a todo, tanto los Jets como los Mariners clasificaron a la edición de la Liga de Campeones de la AFC de la siguiente temporada como campeones y subcampeones, respectivamente.

Temporada 2008/2009

Tras el campeonato logrado en 2008 frente a los Mariners, muchos jugadores partieron del equipo. Entre ellos estuvieron Mark Bridge y Stuart Musialik (al Sydney FC) y Andrew Durante y Troy Hearfield (al Wellington Phoenix). También hubo rumores sobre la posible partida del capitán Jade North y Adam Griffiths tras los partidos de sus con los Socceroos ante Selección de fútbol de Singapur y Selección de fútbol de China, pero ellos prefirieron seguir en el plantel al comienzo de la temporada 2008/2009.​​​

Además, también se especuló con la llegada del defensor Adrian Madaschi y del ex Melbourne Victory, Ljubo Milicevic. Los rumores persistían y aumentaban, tras la noticia del posible retorno de Ryan Griffiths, completando así el trío de los hermanos Griffiths (en el club ya estaban Adam y Joel). Pero toda posibilidad se esfumó tras el préstamo del jugador al Liaoning FC de China desde el Rapid Bucarest rumano, club donde militaba el jugador.​

Muchos de los jugadores que han abandonado el club han sugerido los reajustes salariales como el principal problema, debido a que el dueño del club, Con Constantine, se niega a permitir a los jugadores que usen los acuerdos de servicios para obtener una mayor flexibilidad bajo el tope salarial.​​

El delantero Jason Naidovski fue el primero en fichar por el club en la temporada 2008/2009, llegando desde el Australian Institute of Sport (Instituto Australiano del Deporte), seguido del centrocampista Shaun Ontong (proveniente del Adelaide United) y de la promesa del seleccionado sub-20 australiano, Kaz Patafta, que lleva proveniente del Benfica de Portugal.​ Después de la contratación del defensa Antun Kovacic llegaron el danés Jesper Håkansson y el internacional ecuatoriano Edmundo Zura.

Los Jets comenzaron la temporada con la participación en la Copa de Pretemporada, donde obtuvieron 2 empates y 1 derrota, quedando en el tercer puesto en su grupo, por detrás del Melbourne Victory y del Adelaide United. Terminaron en octavo lugar ese año, por lo que no pudieron disputar la fase final.