Si era diplomato al Liceo di Cagliari e, all'indomani della marcia su Roma, aveva aderito alla Federazione giovanile comunista. Quando, nel 1923, la sua famiglia si trasferì a Rodi, dove il padre di Velio aveva ottenuto un importante incarico nell'amministrazione fascista dell'Isola, il giovane cominciò a frequentare Giurisprudenza all'Università di Roma e, nella Capitale, entrò nel Comitato federale della gioventù comunista.
Fermato e schedato durante le manifestazioni studentesche seguite all'assassinio di Giacomo Matteotti, Spano decide di trasferirsi all'Università di Torino per continuare l'attività tra gli studenti, meglio evitando i controlli della polizia. Ma sul finire del 1926, dopo la proclamazione delle Leggi eccezionali fasciste, lo studente è costretto a passare completamente all'attività clandestina. Nel 1927 è tra i redattori di Il Goliardo rosso, del Fronte unico, del Fanciullo proletario.
Nonostante le precauzioni, Spano finisce per essere arrestato. Una condanna a due mesi di reclusione e l'invio al confino non bastano. Il 12 aprile del 1928 il Tribunale speciale gli infligge cinque anni e cinque mesi di reclusione per "associazione e propaganda comunista".
Quando riacquista la libertà, il giovane comunista passa in Francia e per due anni s'impegna nell'apparato del Centro estero del suo partito che, nel 1935, con l'aggressione fascista all'Etiopia, lo manda in Egitto: con il nome di copertura di Paul Conibet, Spano fa propaganda tra i soldati italiani in transito dal Canale di Suez. Ancora due anni di missioni clandestine in Italia, poi il passaggio in Spagna per la lotta antifranchista.
Nello stato maggiore del generale Juan Modesto, Paolo Tedeschi (questo il nuovo nome di copertura), lavora all'emittente radiofonica che, sotto il titolo di "Radio Milano", trasmette da Madrid, in italiano, per le truppe del corpo di spedizione fascista. Nell'autunno del 1937, nuovo trasferimento di Spano a Parigi. Si occupa dell'edizione clandestina de l'Unità. L'anno dopo è già in Tunisia, a redigere il quotidiano antifascista Il Giornale, sino a che Mussolini dichiara guerra alla Francia e Spano, cittadino di origine italiana, è internato dalle autorità francesi nel campo di Beitla.
La capitolazione della Francia determina, per Spano, il ritorno alla lotta clandestina. E' tra gli organizzatori del Partito comunista tunisino, è in contatto con i socialisti francesi contrari al governo di Vichy e con gli indipendentisti tunisini di Habib Bourghiba. Nel novembre del 1941, per una delazione, i quadri del PCT sono arrestati in massa. "Paolo Tedeschi" riesce ad evitare la cattura, ma non la condanna a morte in contumacia in due successivi processi.
Riprende l'attività clandestina e dopo l'occupazione italiana della Tunisia, riesce anche a diffondere tra le nostre truppe Il Soldato italiano, un giornale di propaganda antifascista. Nell'ottobre 1943, con la moglie Nadia Gallico, torna fortunosamente in Italia. A Napoli dirige l'edizione meridionale de l'Unità, entra nella Direzione del PCI e, dopo la liberazione di Roma, dirige l'organo del suo partito sino al giugno 1946.
Consultore nazionale nel 1945, Velio Spano è membro dell'Assemblea Costituente dal 1946 al 1948. Sottosegretario all'Agricoltura nel secondo Gabinetto De Gasperi, senatore nel 1948, Spano è stato per dieci anni responsabile dell'organizzazione regionale sarda del PCI. Nel 1957 gli fu affidata la direzione della Sezione Esteri del Comitato centrale del suo partito e due anni dopo fu nominato segretario del Movimento italiano per la pace.