W roku 1613 śląski regionalista i historyk Mikołaj Henel z Prudnika wymienił miejscowość w swoim dziele o geografii Śląska pt. Silesiographia podając jej łacińską nazwę: Bicina.
Nazwa pochodzi od wyrazu pospolitego byczyna oznaczającego miejsce hodowli i wypasu byków lub od nazwy osobowej Bycza, która pochodzi od wyrazu byk. Nazwa Byczyna została zniemczona jako Bitschin, później Pitschen. Nazwę Pitschen odnotowano po raz pierwszy w dokumencie handlowym książąt Ludwika II i Henryka IX z 31 maja 1400 roku.
W 1945 roku nastąpiło objęcie miasta przez polską administrację. W 1946 roku wprowadzono aktualną nazwę.
Legenda powstania nazwy miasta mały|lewo|Plan centrum Byczyny (przed 1939) Jednym z dominujących w okolicy pagórków jest położone na wschód od Byczyny tzw. Wzgórze Krzyżowe, nad którym od niepamiętnych czasów miały krzyżować się drogi handlowe. Legenda głosi, że w miejscu tym, z którego widok rozciąga się na wiele kilometrów, pewnego razu zatrzymali się wędrowcy, podróżujący wraz z dobytkiem. Tutaj czuli się bezpieczni, bowiem dzięki korzystnemu usytuowaniu wzgórza nie mogli być znienacka zaskoczeni przez wroga. Wówczas to byczek ze stada owych wędrowców, grzebiąc racicą w ziemi natrafił na naczynie wypełnione złotymi monetami.