We observe interspecies Feshbach resonances due to s-wave bound states in ultracold K-39-Cs-133 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 K-39-Cs, K-40-Cs, and K-41-Cs. Our results open up the possibilities of tuning interactions in K-Cs atomic mixtures and of producing ultracold KCs molecules.