El Club de Lucha Viña Nava fue fundado en la localidad que lleva su nombre, que forma parte del lagunero Barrio Nuevo, ubicado al sureste del casco municipal y al oeste del barrio La Verdellada, cruzado por el barranco de Gonzaliánez. El primer apunte que tenemos de este club data del año 1957, cuando, con fecha 1 de octubre, tramitó sus estatutos en el Registro del Gobierno Civil de la provincia de Santa Cruz de Tenerife denominándose Sociedad Deportiva Viña Nava, cuyo domicilio social se fijó en la calle G, número 17, de Viña Nava. Los integrantes de la comisión organizadora fueron Jesús Acosta Rodríguez, Evelio Álvarez Acosta, Basilio Hernández González, Antonio de la Rosa Coello, Manuel Álvarez Acosta, Raúl Ramos González, Francisco Cruz Díaz e Hipólito Cruz Díaz. De esa fecha no tenemos constancia de participación alguna, ni siquiera amistosa.
El 30 de noviembre de 1966 volvieron a tramitar sus estatutos, otra vez en el Gobierno Civil de la provincia de Santa Cruz de Tenerife, como Viña Nava Club de Lucha y sito en el barrio Viña Nava. Los organizadores esa vez eran Sergio Miguel Fernández Torres (presidente), Evaristo González Rodríguez (vicepresidente), Pedro Marrero Torres (secretario), Álvaro Domínguez de la Rosa (tesorero) y Ricardo Simó Pérez y Gregorio Expósito Delgado en la condición de vocales.
Y de esa manera avanzó hacia su primera participación en competiciones oficiales, por lo que, al amparo de la Federación Tinerfeña de Luchas, confirmó su presencia en la temporada 1967-1968 con un equipo de segunda categoría y otro juvenil, integrado este en el CL Santa Cruz como filial. Ese curso compitieron contra el Brisas del Teide, Chimisay, Naranjo, Sobradillo, Tijarafe, Unión Canteras, UD Tacuense y Unión Rosario. Sus luchadores más habituales eran Manuel Expósito, el Trota; el palmero Manolín Acosta; Gumersindo González; Óscar Expósito; los hermanos Francisco y José Cruz; Eugenio Emilio Estévez, Geño; Laudelino Rodríguez, conocido como Nino el Chopa; Ángel Domingo Pérez, Tato; José e Hilario Baussou; Santiago Díaz; José Pérez; Pepe Barranquera; Agustín Lalo Mesa, Mesa II; Eulogio Afonso; Benito Bacallado; Ramón Oliva; Justo Brito; Francisco Carrión; y los juveniles procedentes del Santa Cruz que reforzaban puntualmente al equipo: Juan Arvelo Valencia y José Antonio González, Trota II.
El 16 de mayo de 1968, de la temporada 1968-1969, constituyeron nueva junta directiva con Alfonso de la Rosa Díaz (presidente), Manuel del Castillo Martín (vicepresidente primero), Evaristo González Rodríguez (vicepresidente segundo), José Ramón Domínguez Torres (secretario), Fernando González Hernández (vicesecretario), Adrián Amador Rodríguez (tesorero), Pascual Marrero Trujillo (contador) y los vocales Sergio M. Fernández Torres, Manuel de Vera Miranda, Valentín Álvarez de Dios, Juan Rivero Reyes, Ricardo Simó Pérez, Gregorio Expósito Delgado, Óscar Expósito Rodríguez y Juan Manuel Ramos Cáceres. Fue cuando compartieron grupo de segunda categoría con sus homólogos del Brisas del Teide, Chimisay, Tijarafe y Unión Canteras. Sería el inicio de su permanente despedida de la práctica activa.
Parte de sus luchadores más destacados ese segundo año fueron Miguel Alonso; Manuel González; José Luis Rodríguez, Chivi; Juan Miguel Martín; Arcadio Reverón; los hermanos Francisco y José Cruz; Nino el Chopa; Antonio Molina; José Manuel Baussón; Juan N. Galván; Eulogio Alonso; Benito Bacallado; Ramón Oliva; Juan Afonso; Hipólito Ramos; y Óscar Expósito.
