Germanium (Ge) is a vital element for applications that operate in near-infrared wavelengths. Recent progress in developing nanostructured Ge surfaces has resulted in >99% absorption in a wide wavelength range (300-1700 nm), promising unprecedented performance for optoelectronic devices. However, excellent optics alone is not enough for most of the devices (e.g. PIN photodiodes and solar cells) but efficient surface passivation is also essential. In this work, we tackle this challenge by applying extensive surface and interface characterization including transmission electron microscopy and x-ray photoelectron spectroscopy, which reveals the limiting factors for surface recombination velocity (SRV) of the nanostructures. With the help of the obtained results, we develop a surface passivation scheme consisting of atomic-layer-deposited aluminum oxide and sequential chemical treatment. We achieve SRV as low as 30 cm s^-1 combined with similar to ~1% reflectance all the way from ultraviolet to NIR. Finally, we discuss the impact of the achieved results on the performance of Ge-based optoelectronic applications, such as photodetectors and thermophotovoltaic cells.