The Kitaev quantum spin liquid displays the fractionalization of quantum spins into Majorana fermions. The emergent Majorana edge current is predicted to manifest itself in the form of a finite thermal Hall effect, a feature commonly discussed in topological superconductors. Here we report on thermal Hall conductivity $kappa_{xy}$ measurements in $alpha$-RuCl$_3$, a candidate Kitaev magnet with the two-dimensional honeycomb lattice. In a spin-liquid (Kitaev paramagnetic) state below the temperature characterized by the Kitaev interaction $J_K/k_B sim 80$ K, positive $kappa_{xy}$ develops gradually upon cooling, demonstrating the presence of highly unusual itinerant excitations. Although the zero-temperature property is masked by the magnetic ordering at $T_N=7$ K, the sign, magnitude, and $T$-dependence of $kappa_{xy}/T$ at intermediate temperatures follows the predicted trend of the itinerant Majorana excitations.