Dio menos conciertos que antes, pero en 1958 tuvo el primero de los que a veces serían largos contratos con el Half Note Club de Nueva York, después de que los dueños le persuadieran para dar presentaciones, en parte porque reemplazaron su piano Steinwaycon un nuevo Bechstein que fue elección de Tristano.