We observe interspecies Feshbach resonances due to s-wave bound states in ultracold $^{39}$K-$^{133}$Cs scattering for three different spin mixtures. The resonances are observed as joint atom loss and heating of the K sample. We perform least-squares fits to obtain improved K-Cs interaction potentials that reproduce the observed resonances, and carry out coupled-channel calculations to characterize the scattering and bound-state properties for $^{39}$K-Cs, $^{40}$K-Cs and $^{41}$K-Cs. Our results open up the possibilities of tuning interactions in K-Cs atomic mixtures and of producing ultracold KCs molecules.