José Luandino Vieira Mateus de Graça, som är hans fullständiga namn, föddes i Lagoa do Furadouro i Portugal. Som liten pojke utvandrade han 1938 med sin familj till Angola, där han växte upp i Luandas kåkstäder. Fadern var skomakare och hade en liten verkstad med ett par tre anställda. Familjen tillhörde de koloniala invandrarna i Angola, vilket innebar att de hade det lite bättre ställt än angolanerna. Men den s.k. lille kolonisatören, arbetaren och hantverkaren, stod längst ner på skalan bland de vita. Ur den aspekten tillhörde Vieira samma klass som sina lekkamrater, de afrikanska barnen. Vieira har sagt i en intervju att det var bland dessa kamrater och lekar som hans förhållningssätt till livet grundlades. De värden han sätter högt är vänskap, kamratskap och lojalitet, allt detta lärde han sig i sin barndom på gatorna i "musseques" (benämning på de fattiga stadsdelarna i Luanda). De var en grupp pojkar som höll ihop, svarta, färgade och portugiser och de betraktade sig som angolaner. När de var i 11-årsåldern gav de ut vad de själva kallade en politisk litterär tidskrift. Den var handskriven och kom ut i ett exemplar som sedan cirkulerade. Vieira minns dessa texter som tämligen dåliga men med en klar ståndpunkt mot kolonialism och förtryck. Under de tidiga tonåren kom Vieira i kontakt med personer som Antonio Jacinto och Agostinho Neto, två av motståndsrörelsens MPLA:s grundare. Under gymnasieåren blev han också bekant med världslitteraturen. Två författare som gjorde intryck på honom var Knut Hamsun och Selma Lagerlöf. Detta sammantaget med livliga diskussioner mynnade ut i en politisk medvetenhet.