He hosted his own television talk show , The Arsenio Hall Show , from 1989 to 1994 on the Fox network . He is best known for his talk show The Arsenio Hall Show , which ran between 1989 and 1994 , and his roles in the films Coming to America and Harlem Nights .