Il progetto Nodo Gordiano nasce all'inizio del 1994 dall'incontro tra Andrea De Luca (basso, voce), Alessandro Papotto (fiati, voce) e Tony Zito (batteria).Con una serie di concerti tra il 1995 e il 1996 la band comincia a farsi notare nell'ambiente delle radio private romane e Radio Rock presenta il Nodo Gordiano nelle principali manifestazioni live.
Nel 1997 il gruppo, tcompone e registra per fini promozionali il materiale che diventerà il primo album in studio omonimo, pubblicato nel 1999 dall'etichetta Lizard, e accompagna dal vivo John Wetton, eseguendo cover dei King Crimson.
L'anno seguente, trasformata la band in sestetto , collabora con il Banco del Mutuo Soccorso (esibendosi anche dal vivo con Francesco di Giacomo alla voce e Rodolfo Maltese alla chitarra), compare sulle reti televisive nazionali in occasione del trentennale del Banco e partecipa a diversi festival.

Nel 2002 Andrea incontra il batterista Carlo Fattorini e il chitarrista Fabrizio Santoro. Prende così forma un trio, aperto, come nella tradizione della band, ad ogni forma di sperimentazione e collaborazione . Una registrazione in presa diretta del brano Lament dei King Crimson viene scelta nel 2003 dall'etichetta Mellow Records per il tributo The Letters. Nel 2004 Fabrizio decide di abbandonare il progetto per dedicarsi al basso elettrico. La band, che già aveva cominciato a comporre del materiale per il nuovo album, si ricostituisce in forma di trio con l'ingresso del tastierista Gianluca Cottarelli. Dalle sessioni di improvvisazione ad alea controllata viene selezionato il materiale che andrà a comporre il secondo album in studio, Alea, impreziosito dal lavoro grafico della pittrice Carla Nico e pubblicato nel 2005 dall'etichetta Mellow Records.
Nel 2007 Andrea e Carlo allestiscono lo studio di registrazione nel quale prende forma il nuovo album Flektogon, pubblicato nel 2009 dall'etichetta AMS/Vynil Magic.
Nel 2013, dopo il ritorno di Fabrizio Santoro alla chitarra, la band torna in studio per la realizzazione dell'album NOUS e per allestire un nuovo repertorio live.
L'uscita dell'album, sempre con la label AMS, è prevista per il 16 Marzo 2014, anno in cui ricorrono i due decenni di attività della band..