Γεννήθηκε στο Αϊβαλί της Μικράς Ασίας το 1904. Ήρθε στην Ελλάδα πριν από τη Μικρασιατική Καταστροφή και εγκαταστάθηκε στον Πειραιά. Εργάστηκε από παιδική ηλικία, όμως η ενασχόληση με την μουσική και το τραγούδι ήταν το μεγάλο του πάθος. Σύντομα ήρθε σε επαφή με τους ρεμπέτες του Πειραιά. Μαζί με τους Μάρκο Βαμβακάρη, Ανέστη Δελιά και Γιώργο Μπάτη έφτιαξαν την πρώτη αμιγώς ρεμπέτικη ορχήστρα. Ήταν γνωστή ως «Τετράς του Πειραιώς», στην καθαρευουσιάνικη εκδοχή του Μπάτη.

Το 1934 η κομπανία πρωτοεμφανίζεται στη μάντρα του Σαραντόπουλου, στην Ανάσταση του Πειραιά και γνωρίζει πολύ μεγάλη επιτυχία. Στην κομπανία τραγουδούν όλοι, όμως ο Παγιουμτζής είναι ο κύριος τραγουδιστής. Την ίδια χρονιά, ο Βαμβακάρης ετοιμάζεται να ηχογραφήσει τον πρώτο του δίσκο. Πηγαίνει στην εταιρία για να παίξει τα τραγούδια του, αλλά όχι και να τα τραγουδήσει, καθώς η κομπανία είχε ως κύριο τραγουδιστή τον Παγιουμτζή, ενώ και ο ίδιος ο Βαμβακάρης δεν πίστευε στις φωνητικές του ικανότητες. Όμως, ο Σπύρος Περιστέρης, ο μαέστρος της εταιρίας, επιμένει να είναι ο Μάρκος ο ερμηνευτής των τραγουδιών του. Έτσι, λοιπόν, ενώ στο λαϊκό πάλκο τα τραγούδια του Βαμβακάρη ερμηνεύονταν από τον Παγιουμτζή, στη δισκογραφία τα τραγουδούσε ο ίδιος ο Βαμβακάρης.