Worldwide, potato (Solanum tuberosum L.) is the third most important food crop after rice and wheat. Its production is however constrained by several virus diseases. The occurrence and distribution of the economically important viruses and associated insect vectors is however not known for Rwanda and Burundi, where potato is an important food security and income crop. We surveyed 194 potato fields for viruses and insect vectors. Aphids were commonly found infesting farmers’ potato fields in contrast to whiteflies. Testing by Enzyme Linked Immunosorbent Assay (ELISA) for six potato viruses identified five viruses: potato leafroll virus (PLRV), potato virus X, S, M and Y (PVX, PVS, PVM, PVY) in Rwanda and two viruses (PLRV and PVS) in Burundi. A subset of samples were analyzed using small RNA sequencing and assembly (sRSA) and additionally revealed presence of PVX and for the first time, tobacco rattle virus (TRV) in Burundi. PLRV and PVS were most common while PVY was rare and not found in Burundi, which is highly unusual. To our knowledge, this is the first report of TRV infecting potatoes in sub-Saharan Africa. Phylogenetic analysis of 14 complete viral genomes determined by sRSA suggested multiple introductions of viruses into the region.