La Estrella Club de Luchas se fundó en 1966 en la realejera calle Toscas de Romero (domicilio social), y fue el tercero en constituirse en ese municipio. Con fecha 15 de diciembre de dicho año tramitó sus estatutos, ante el Registro del Gobierno Civil de la provincia de Santa Cruz de Tenerife, bajo la denominación citada, aunque se le conoció popularmente como el Icod el Alto. La comisión organizadora encargada de la constitución del club y al mismo tiempo como su primera junta directiva estuvo integrada por Manuel Dévora Hernández (presidente), Manuel García Morales (vicepresidente), Julio Mesa Borges (secretario) y Luciano Salazar Luis (tesorero). Posteriormente, con fecha de entrada en la Federación Tinerfeña de Luchas el 28 de junio de 1967, se informó de la reestructuración completa de la junta directiva, que esa vez quedó conformada por Isidro Dorta González (presidente), Antonio Mesa González (vicepresidente), Ruperto Domínguez Rodríguez (secretario), Manuel Jorge Díaz (tesorero) y Pedro Rodríguez Dorta (vocal).
Su estreno en competición oficial, organizada entonces por la institución federativa citada, fue en la temporada 1967-1968 como militante en tercera categoría. El equipo fue incluido en el grupo de la zona La Orotava, que reunía a los equipos del valle orotavense y en el que les tocó competir contra el Águila Negra, Atlante, Candelaria del Norte, Candias, Cruz Santa, Palo Blanco, Perdoma y Pinoleris.
Los luchadores de La Estrella en su inicio oficial fueron Manuel Grillo, Celso Alonso, Julián González, Juan González, Julio Mesa, Juan Quintero, Isabelino Torres, Vicente Luis, Benito Felipe, Antonio Rodríguez, Joaquín Felipe, los hermanos Vicente y Luis Alejo Torres Grillo, Hermógenes Delgado, Mariano Delgado, Roque García, Francisco Yanes, Juan Báez, Octavio Rodríguez, Leopoldo Goya, Francisco Goya, Manuel Pérez, José Hernández, Benito García, Severiano García, Felipe González, Eleuterio Fleitas, Manuel Gutiérrez y José Fernández, entre otros.
Para la temporada siguiente (1968-1969), con fecha 12 de agosto de 1968, decidieron oficiar nueva junta directiva con esta relación de nombres y cargos: Isidro Dorta González (presidente), Luis Fuentes León (vicepresidente), Julio Hernández Guerra (secretario) y Juan de León García (tesorero). El equipo volvió a participar en tercera categoría, aunque esa vez como parte del grupo norte junto con el Águila Negra, Atlante, Calvario, Candelaria del Norte, Candias, Echeide, Guanche, Montañeta, Palo Blanco, Perdoma, Punta Brava, Real Unión Agua García y Unión Florida.
El CL La Estrella incorporó en su segunda temporada a los bregadores Lucio Esteban Hernández, Estebita (como puntal); Juan Rodríguez; Adolfo Hernández; Pedro Bacallado; Adolfo Niz; Jesús Rodríguez; Eleuterio Mesa; y Sebastián Torres.
