We study a non-archimedean (NA) version of transportation problems and introduce naturally arising ultra-norms which we call Kantorovich ultra-norms. For every ultra-metric space and every NA valued field (e.g., the field $mathbb Q_{p}$ of $p$-adic numbers) the naturally defined inf-max cost formula achieves its infimum. We also present