We study the evolution of extremely metal-poor AGB stars, with metallicities down to [Fe/H]=-5, to understand the main evolutionary properties, the efficiency of the processes able to alter their surface chemical composition and to determine the gas and dust yields. We calculate two sets of evolutionary sequences of stars in the 1-7.5Msun mass range, evolved from the pre-main sequence to the end of the AGB phase. To explore the extremely metal-poor chemistries we adopted the metallicities Z=3x10^{-5} and Z=3x10^{-7} which correspond, respectively to [Fe/H]=-3 and [Fe/H]=-5. The results from stellar evolution modelling are used to calculate the yields of the individual chemical species. We also modelled dust formation in the wind, to determine the dust produced by these objects. The evolution of AGB stars in the extremely metal-poor domain explored here proves tremendously sensitive to the initial mass of the star. M<2Msun stars experience several third dredge-up events, which favour the gradual surface enrichment of C12 and the formation of significant quantities of carbonaceous dust, of the order of 0.01Msun. The C13 and nitrogen yiel are found to be significantly smaller than in previous explorations of low-mass, metal-poor AGB stars, owing to the weaker proton ingestion episodes experienced during the initial AGB phases. M>5Msun stars experience hot bottom burning and their surface chemistry reflects the equilibria of a very advanced proton-capture nucleosynthesis; little dust production takes place in their wind. Intermediate mass stars experience both third dredge-up and hot bottom burning: they prove efficient producers of nitrogen, which is formed by proton captures on C12 nuclei of primary origin dredged-up from the internal regions.