Εμβληματικός τραγουδιστής της κλασσικής εποχής του ρεμπέτικου. Είπαν χαρακτηριστικά γι’ αυτόν ότι «στο λαιμό του είχε φωλιές από αηδόνια». Γεννήθηκε στο Αϊβαλί της Μικράς Ασίας το 1904. Ήλθε στην Ελλάδα πριν από τη Μικρασιατική Καταστροφή και εγκαταστάθηκε στον Πειραιά.
Από παιδί μπήκε στο μεροκάματο, αλλά το μεγάλο πάθος του ήταν το τραγούδι. Γρήγορα γνωρίστηκε με την πειραιώτικη παρέα του ρεμπέτικου. Μαζί με τους Μάρκο Βαμβακάρη, Ανέστη Δελιά και Γιώργο Μπάτη έφτιαξαν την πρώτη αμιγώς μπουζουξίδικη λαϊκή ορχήστρα. Ήταν γνωστή ως «Τετράς του Πειραιώς», στην καθαρευουσιάνικη εκδοχή του Μπάτη.
Το 1934 η κομπανία πρωτοεμφανίζεται στη μάντρα του Σαραντόπουλου, στην Ανάσταση του Πειραιά και γνωρίζει πολύ μεγάλη επιτυχία. Στην κομπανία τραγουδούν όλοι, όμως ο Στράτος είναι ο βασικός τραγουδιστής. Την ίδια χρονιά, ο Μάρκος ετοιμάζεται να ηχογραφήσει τον πρώτο του δίσκο. Ο Μάρκος πηγαίνει στην εταιρία για να παίξει τα τραγούδια του, αλλά όχι και να τα τραγουδήσει, καθώς η κομπανία είχε βασικό τραγουδιστή τον Στράτο και ο ίδιος δεν πίστευε στις φωνητικές του ικανότητες. Όμως, ο Σπύρος Περιστέρης, ο μαέστρος της εταιρίας, επιμένει να είναι ο Μάρκος ο ερμηνευτής των τραγουδιών του. Έτσι, δημιουργείται το εξής παράδοξο: Στο λαϊκό πάλκο τα τραγούδια του Μάρκου να ερμηνεύονται από το Στράτο και στη δισκογραφία από τον Μάρκο.
Την ίδια περίοδο εμφανίζεται στη δισκογραφία και ο Γιώργος Μπάτης. Ηχογραφεί πρώτα το τραγούδι «Μπάτης ο δερβίσης» και ετοιμάζεται να ηχογραφήσει το «Ζεϊμπεκάνο σπανιόλο». Η κομπανία προβάρει το τραγούδι, ο Μπάτης όμως δεν μπορεί να τραγουδήσει κι έτσι ηχογραφείται με τη φωνή του Στράτου. Ακολουθούν τα τραγούδια «Οι σφουγγαράδες» και «Μάγκες καραβοτσακισμένοι» και το 1936 ο Στράτος ερμηνεύει τραγούδια και του τέταρτου της παρέας, του Ανέστη Δελιά («Μάγκες πιάστε τα βουνά», «Τον άντρα σου και μένα» κ.ά.).
Στα πρώτα χρόνια της δισκογραφικής παρουσίας των Πειραιωτών ο Στράτος συμμετέχει στις περισσότερες ηχογραφήσεις, ακόμα κι όταν δεν τραγουδάει. Σε πολλά απ’ τα πρώτα τραγούδια του Μάρκου παίζει μπαγλαμά ή ποτηράκια, ενώ δεκάδες είναι οι δίσκοι όπου η φωνή του χαιρετίζει τους συμμετέχοντες στην ηχογράφηση («Γεια σου Μάρκο με τις ζωντανές σου τις πενιές σου», «Γεια σου Σπύρο μου με το μπουζουκάκι σου»). Καμιά φορά χαιρετίζει και τον εαυτό του! («Γεια σου και σένα ρε Στράτο με τον τζουρά σου»).
Στα μέσα της δεκαετίας του ’30 η φωνή του Στράτου Παγιουμτζή είναι ήδη μύθος. Από τότε αναφέρεται μόνο με το μικρό του όνομα, ακόμα και σε ετικέτες δίσκων. Το 1935 τον χρησιμοποιεί ως ερμηνευτή ο Βαγγέλης Παπάζογλου («Σαν εγύριζα απ’ την Πύλο») και από το 1937 και άλλοι μεγάλοι Μικρασιάτες δημιουργοί: Ο Παναγιώτης Τούντας («Περσεφόνη μου γλυκιά», «Είν’ ευτυχής ο άνθρωπος» κ.ά.), ο Κώστας Σκαρβέλης («Σε γελάσανε», «Ο κόσμος πλούτη λαχταρά» κ.ά.) και ο Σπύρος Περιστέρης («Θαλασσινό μεράκι», «Για σένα μαυρομάτα μου» κ.ά.).
Το 1938 ο Στράτος θα τραγουδήσει Μανώλη Χιώτη («Δε λες το ναι και συ») και μερικά απ’ τα καλύτερα τραγούδια του Μπαγιαντέρα («Γυρνώ σαν Νυχτερίδα», «Χατζηκυριάκειο»). Με τον Τσιτσάνη είχε γνωριστεί μερικούς μήνες νωρίτερα και μαζί του θα ξεκινήσει μια πολύχρονη συνεργασία. Δεκάδες πασίγνωστα τραγούδια του Τσιτσάνη πρωτοηχογραφήθηκαν με τη φωνή του Στράτου Παγιουμτζή, κάτι που δεν είναι καθόλου άσχετο με την επιτυχία τους.
Μετά την Κατοχή, ο Στράτος συνεχίζει τη συνεργασία του με τους παλιότερους λαϊκούς δημιουργούς (Μάρκο, Τσιτσάνη, Χιώτη κλπ.) και με νέους, όπως ο Απόστολος Καλδάρας («Πάνω σ’ ένα βράχο») και ο Γιώργος Μητσάκης («Μάγκας βγήκε για σεργιάνι»). Θα συνεχίσει στη δισκογραφία ως τα μέσα της δεκαετίας του ’50, οπότε με την άνθηση του αρχοντορεμπέτικου η καριέρα του θα πάρει την κατιούσα.
Στις αρχές της δεκαετίας του ’60 ο Ζαμπέτας τον ξαναφέρνει στο προσκήνιο, εκμεταλλευόμενος τη μεγάλη του επιρροή στις εταιρίες. Ο Στράτος ηχογραφεί προπολεμικά ρεμπέτικα του Χατζηχρήστου, του Τσιτσάνη και άλλων δημιουργών, τον περίφημο αμανέ «Μινόρε του Στράτου» και τον ύμνο του Ολυμπιακού «Ολυμπιακέ μεγάλε, Ολυμπιακέ τρανέ» («Ολυμπιακέ μεγάλε, Ολυμπιακέ τρανέ / που εσάρωσες τη Σάντος, την ομάδα του Πελέ). Εκτός απ’ τη δισκογραφία, ο Στράτος επανέρχεται στα λαϊκά πάλκα, όπου δούλευε ασταμάτητα απ’ το 1934 έως το 1955.
Τον Οκτώβρη του 1971 καταφέρνει να βγάλει διαβατήριο (το 1937 είχε συλληφθεί για χρήση χασίς και πήγε εξορία) και να πάει στη Νέα Υόρκη. Δούλεψε στη «Σπηλιά», όπου αποθεωνόταν απ’ τους ομογενείς. Στις 16 Νοεμβρίου 1971 «έσβησε» πάνω στο πάλκο, σε ηλικία 67 ετών. Για να τον γυρίσουν στην πατρίδα και να τον κηδέψουν, χρειάστηκε να γίνει έρανος από παλιούς φίλους και συνεργάτες του, ενώ τα έξοδα της κηδείας κάλυψε ο Γιώργος Ζαμπέτας.