The station first signed on the air on September 1, 1991 as KLSB-TV, operating as a satellite station of NBC affiliate KETK-TV (channel 56). KLSB-TV covered the southern portion of the market while KETK served the northern side. KETK and KLSB-TV were branded as "Region 56" and "Region 19," respectively. Max Media (a company partially related to Max Media Properties, former owner of KETK) purchased the station in 2003. Upon acquiring the station, Max Media signed an affiliation agreement to become the market's CBS affiliate. The company also leased a building in southeast Tyler that formerly operated as a four-screen movie theater to serve as the station's studio facilities. That winter, Max filed an application with the Federal Communications Commission (FCC) to change the station's callsign to KYTX. Channel 19 officially joined CBS on April 12, 2004, broadcasting from the KLSB transmitter; the following day, the FCC officially granted the call sign change to KYTX (the KLSB callsign ended up on a low-power station broadcasting on UHF channel 53, which became the sole repeater of KETK, until it shut down in 2012). The station relocated its transmitter facilities to new tower located south of New Summerfield on June 13, 2004. The new transmitter facilities provided an upgraded signal that allowed KYTX to cover both the Tyler–Longview and Lufkin–Nacogdoches areas. The city of license has remained Nacogdoches.