We have observed a softening of phonons and a structural phase transition in a superconducting Ba0.59K0.41BiO3 (Tc = 31 K) single crystal using elastic and inelastic neutron scattering measurements. The soft phonon occurs for the [111] transverse acoustic mode at the zone boundary. The phonon energies in this vicinity are found to continuously decrease with decreasing temperature from above room temperature to 200 K, where a structural phase transition from cubic to tetragonal symmetry occurs. The overall results are consistent with previous data that reported phonon softening and a (0.5, 0.5, 0.5) type superstructure in several Ba1-xKxBiO3 systems. However, we also find weak (0.5, 0.5, 0) type superstructure peaks that reveal an additional component to the modulation. No significant change related to the superconductivity was observed for the soft phonon energies or linewidths.