El 15 de julio de 1959 se anunció que Presley, tras su liberación del ejército estadounidense, haría su primera aparición televisiva en el cuarto y último programa de variedades patrocinado por Timex de Frank Sinatra. Para el especial, originalmente titulado Frank Sinatra's Welcome Home Party for Elvis Presley , recibiría 125 000 dólares, una suma inaudita en aquel momento para una sola aparición televisiva. Sinatra no estaba contento con los honorarios de Presley, sabiendo muy bien que excedían su compensación por presentar el programa completo.^[1]​ ^[2]​ Aceptó, consciente de que una aparición de Presley atraería enormes índices de audiencia por hora, algo que sus tres especiales anteriores no habían logrado hacer. ^[2]​ El representante de Presley, el coronel Tom Parker , también dejó muy claro que esta suma era solo para dos canciones, de aproximadamente 6 a 8 minutos. ^[3]​

Parker esperaba que presentar a Presley en el programa de Sinatra lo introduciría a un público mayor, un público más maduro, menos propenso a descartarlo en favor del próximo ídolo adolescente. ^[4]​ El especial de televisión reuniría a dos de las estrellas más grandes del mundo de la música, cada una con sus propios títulos legendarios: Sinatra era conocido como "la Voz" y Presley era conocido como "el Rey" . Al darse cuenta de la publicidad de tal evento mediático, Parker estaba decidido a que esta oportunidad se desarrollara de la mejor manera posible para su cliente. ^[5]​

El 3 de marzo de 1960, Presley, a los 25 años, regresó a Estados Unidos desde Alemania Occidental. Sinatra había organizado que su hija, Nancy, formara parte de la fiesta de bienvenida, presentándole a Presley una caja de camisas de vestir en nombre de su padre. ^[6]​

Cuando se le preguntó quiénes eran sus cantantes favoritos en ese momento, Presley mencionó a Sinatra junto con Dean Martin , Patti Page y Kitty Kallen . Dos días después, tras dos años de haber sido reclutado en el Ejército de los EE. UU., Presley fue dado de baja honorablemente. ^[7]​ Dos semanas más tarde él estaba en Nashville, Tennessee , para grabar nuevo material para el lanzamiento de un sencillo y un álbum muy esperados. ^[4]​

Dos de las canciones que grabó el 21 de marzo, "Stuck On You" y "Fame And Fortune", fueron elegidas como las dos caras de su primer sencillo después del ejército, y las interpretaría en vivo en el especial de televisión de Sinatra Timex. ^[4]​ El 21 de marzo, después de completar dos canciones adicionales para el álbum, Presley abordó un tren de Nashville a Miami, Florida . Al llegar a Miami al día siguiente, Presley se registró en el Hotel Fontainebleau , el lugar donde se grabaría el espectáculo. ^[2]​ ^[7]​ Pasó el resto de la semana ensayando para el espectáculo, que estaba programado para grabarse el 26 de marzo, y se reunió con Sinatra para promocionarlo en una reunión cuidadosamente preparada que fue fotografiada para el comunicado de prensa. ^[8]​

El encuentro entre ambos fue seguido con interés por los medios de comunicación. ^[8]​ Sinatra y Presley habían sido rivales musicales desde la década de 1950, y en ocasiones se les había preguntado la opinión del otro. Sinatra había escrito un artículo en la revista francesa Western World en 1957, describiendo el rock and roll como "cantado, interpretado y compuesto principalmente por cretinos y mediante sus reiteraciones casi imbéciles y letras astutas, lascivas —de hecho, sucias—, y como dije antes, se las arregla para ser la música marcial de todo delincuente con patillas sobre la faz de la tierra… este afrodisíaco de olor rancio que deploro". ^[9]​

Cuando se le preguntó su reacción al escuchar esto, Presley respondió: "Tiene derecho a su opinión, pero no puedo verlo criticándolo sin una buena razón. Lo admiro como intérprete y actor, pero creo que está muy equivocado en esto. Si mal no recuerdo, también formaba parte de una tendencia. No entiendo cómo puede llamar a la juventud de hoy inmoral y delincuente". La prensa, conocida o desconocida para Sinatra y Presley, estaba intentando causar una ruptura entre la pareja. Sin embargo, solo tenían cosas buenas que decir el uno del otro cuando se les preguntó específicamente cómo se sentían. Sinatra, cuando se le preguntó puntualmente sobre el estilo de canto de Presley, respondió: "Solo el tiempo lo dirá. Dijeron que era un bicho raro cuando empecé, pero todavía sigo por aquí. Presley no tiene ningún entrenamiento. Cuando se dedique a algo más serio, a un tipo de canto más profundo, descubriremos si es cantante. Tiene un talento natural y animal". Por su parte, cuando se le preguntó nuevamente sobre los comentarios anteriores de Sinatra respecto al rock and roll, Presley fue igual de amable con Sinatra: "Admiro al hombre... Es un gran suceso y un buen actor". ^[9]​

Antes de la grabación del programa, le preguntaron a Sinatra si había cambiado de opinión sobre el rock and roll. Insinuó que no, simplemente respondiendo: «El chico lleva dos años fuera, y tengo la sensación de que realmente cree en lo que hace». ^[9]​

El 26 de marzo, a las 18:15 hs, se realizó la grabación del programa en el Hotel Fontainebleau . ^[1]​ ^[10]​ Fue la primera aparición de Presley en televisión en más de tres años, y su primera actuación seria desde 1957, lo que lo puso nervioso sobre cómo sería recibido. ^[11]​

El Coronel Parker, quizás por sus propios nervios, había dispuesto que el público estuviera compuesto por tantos fans de Presley como fuera posible, aunque al menos la mitad seguían siendo fans de Sinatra. Para la ocasión, para encajar con la imagen de rat pack de Sinatra, Presley vistió un esmoquin . ^[11]​

La primera y breve aparición de Presley en el programa fue al principio. Ataviado con su uniforme militar, Presley se unió a los demás invitados, incluyendo a Nancy, la hija de Sinatra, para cantar un fragmento de «It's Nice To Go Trav'ling». ^[12]​ Sus otras dos canciones, «Stuck On You» y «Fame And Fortune», se habían estrenado tan solo unos días antes de la grabación del especial. Presley también actuó con Sinatra, cada uno cantando una canción que el otro había hecho famosa, turnándose para cantar una estrofa cada uno; Presley cantó «Witchcraft» y Sinatra «Love Me Tender». ^[13]​

Antes de comenzar a cantar, durante la introducción musical, ambos cantantes movian rítmicamente sus hombros, a lo que Sinatra alegó mirando hacia las cámaras "Nosotros trabajamos de la misma manera, solo que en diferentes áreas" ^[13]​ Ambas canciones se interpretaron en el estilo swing por el que Sinatra era famoso, aunque la crítica no estuvo de acuerdo en cuanto a su sonido: «Presley tuvo dificultades con la melodía del tema de Sinatra. La sintonía entre ambos en «Love Me Tender» resultó muy armoniosa».^[8]​ ^[11]​

Tras aproximadamente ocho minutos en pantalla y una breve promoción de su nueva película, GI Blues , Presley se marchó. El resto del espectáculo giró en torno a Sinatra y sus amigos del "rat pack". ^[11]​

El programa, ahora titulado The Frank Sinatra Timex Special y patrocinado por Timex Company, se emitió a nivel nacional en ABC-TV la noche del 12 de mayo de 1960 entre las 9:30 y las 10:30 locales. Las cifras de audiencia para el programa fueron altas, con una calificación de Trendex del 41,5 %, aproximadamente el 67,7 % de la audiencia televisiva general. Para poner eso en perspectiva, el segundo programa con mayor audiencia en ese horario, Ernie Ford Show de NBC , con Johnny Cash y You Bet Your Life protagonizado por Groucho Marx , obtuvo una participación de audiencia del 21,1 %

En su libro, Elvis Para Dummies , la autora Susan Doll señala la importancia de este especial de televisión para la carrera de Presley. Escribe: «Aparecer con Sinatra sugería que Elvis seguía la misma trayectoria profesional que Sinatra y, por lo tanto, era el heredero natural de La Voz». También señala que el estilo de canto de Presley y su aparición en el programa «indicaban claramente que Elvis buscaba un público adulto y general».^[5]​

En el libro "Elvis y yo" Priscilla Presley menciona brevemente en uno de los capítulos la participación de Elvis en el show televisivo de Frank Sinatra, ^[14]​

El periodista argentino y escritor Marcelo Gobello, autor de los libros "Rock en el cielo" ^[15]​ "Jim Morrison, un jinete en la tormenta" ^[16]​ y "Elvis, el rey del rock and roll" expresaría lo inimposible que hubiese sido dos años antes imaginar a los dos cantantes más grandes de la historia interpretando en televisión canciones a dúo, a la vez que señalaba lo exitoso de ese evento y que sería la última aparición de Elvis en televisión hasta su especial de regreso en 1968 luego de varios años de contratos para realizar películas en Hollywood.^[17]​

Luego de ese evento Elvis Presley y Frank Sinatra irían forjando una amistad que se mantuvo durante el resto de sus vidas. llegándose a vérselos en eventos públicos en varias oportunidades. Una de ellas fue el 24 de Junio de 1965 mientras Elvis se encontraba filmando la película Frankie and Johnny donde Elvis donó US$ 50.000 a la Motion Pictures Relief Fund. Alli se reunieron con él, Frank Sinatra, Barbara Stanwyck y Budd Abbott, que eran quienes representaban a la fundación, y aceptaron la donación. ^[18]​

Dos años después cuando Elvis y Priscilla contrajeron matrimonio, Sinatra les facilitó su avión privado, el Jet Christina para que se trasladaran hacia la residencia de Palm Spring California donde pasarían su luna de miel. ^[19]​ ^[20]​ También se los pudo ver a ambas celebridades reunidas en Las Vegas durante un evento de apertura de Nancy Sinatra en 1969 ^[21]​ entre otras ocasiones,

Durante su última serie de conciertos en 1977 Elvis recurría a interpretar cada vez más al tema My Way y en su recital en Rapid City menciona a Frank antes de comenzar a cantarla, expresando "The next son was recorded by Frank Sinatra in the disco My Way" ^[22]​ Parte de este concierto, con esta interpretación de My Way en si, fue incorporado en el documental televisivo póstumo titulado Elvis In Concert y el álbum del mismo nombre.

• Elvis Presley y Frank Sinatra "Love Me Tender / Witchcraft" 1960