We report a correlated NanoSIMS-transmission electron microscopy study of the ungrouped carbonaceous chondrite Northwest Africa (NWA) 5958. We identified 10 presolar SiC grains, 2 likely presolar graphite grains, and 20 presolar silicate and/or oxide grains in NWA 5958. We suggest a slight modification of the commonly used classification system for presolar oxides and silicates that better reflects the grains' likely stellar origins. The matrix-normalized presolar SiC abundance in NWA 5958 is $18_{-10}^{+15}$ ppm (2$\sigma$), similar to that seen in many classes of unmetamorphosed chondrites. In contrast, the matrix-normalized abundance of presolar O-rich phases (silicates and oxides) is $30.9_{-13.1}^{+17.8}$ ppm (2$\sigma$), much lower than seen in interplanetary dust particles and the least altered CR, CO and ungrouped C chondrites, but close to that reported for CM chondrites. NanoSIMS mapping also revealed an unusual $^{13}$C-enriched ($\delta ^{13}$C$\sim$ 100--200 permil) carbonaceous rim surrounding a 1.4 $\mu$m diameter phyllosilicate grain. TEM analysis of two presolar grains with a likely origin in asymptotic giant branch stars identified one as enstatite and one as Al-Mg spinel with minor Cr. The enstatite grain amorphized rapidly under the electron beam, suggesting partial hydration. TEM data of NWA 5958 matrix confirm that it has experienced aqueous alteration and support the suggestion of Jacquet et al. (2016) that this meteorite has affinities to CM2 chondrites.