Pirmo kosmisko lidojumu Vinogradovs veica 1997. un 1998. gadā kā kosmosa kuģa Sojuz TM-26 un orbitālā stacijas Mir 24. pamatekspedīcijas bortinženieris. Veica piecas iziešanas kosmosā, lai salabotu stacijas elektroapgādi pēc Spektr moduļa dehermetizācijas.
Trešo lidojumu Pāvels Vinogradovs sāka 2013. gada martā, esot kosmosa kuģa Sojuz TMA-08M komandieris un SKS 35. ekspedīcijas lidojuma inženieris. Bija 36. ekspedīcijas komandieris. 2013. gada septembrī atgriezas uz zemes.