Distributing quantum entanglement on a chip is a crucial step toward realizing scalable quantum processors. Using traveling phonons-quantized guided mechanical wave packets-as a medium to transmit quantum states is now gaining substantial attention due to their small size and low propagation speed compared to other carriers, such as electrons or photons. Moreover, phonons are highly promising candidates to connect heterogeneous quantum systems on a chip, such as microwave and optical photons for long-distance transmission of quantum states via optical fibers. Here, we experimentally demonstrate the feasibility of distributing quantum information using phonons by realizing quantum entanglement between two traveling phonons and creating a time-bin-encoded traveling phononic qubit. The mechanical quantum state is generated in an optomechanical cavity and then launched into a phononic waveguide in which it propagates for around 200 micrometers. We further show how the phononic, together with a photonic qubit, can be used to violate a Bell-type inequality.