The wheat stripe rust fungus (Puccinia striiformis f.sp. tritici) threatens global wheat production. Small RNAs (sRNAs) modulate plant defense induction, and RNA exchange between host and microbe causes cross-kingdom gene silencing, but few examples are known in rust fungi. This study combined sRNA, parallel analysis of RNA ends, and gene expression data to discover sRNA-target pairs on each side of the interaction. Specific wheat 24 nt sRNAs were suppressed, while particular 35 nt fragments were strongly induced upon infection. Wheat sRNAs cleaved fungal transcripts coding for a ribosomal protein and a glycosyl hydrolase effector. Fungal microRNA-like and phased 21 nt sRNAs originated from long inverted repeats near protein coding genes. Fungal sRNAs targeted native transcripts: transposons and kinases; and cross-kingdom transcripts: a wheat nucleotide-binding domain leucine-rich repeat receptor (NLR) and multiple defense-related transcription factor families. This work sheds light on host-microbe coevolution and delivers prospects for developing pathogen control biotechnology.