A nanotip capacitor and associated fabrication method are provided. The method provides a bottom electrode and grows electrically conductive nanotips overlying the bottom electrode. An electrically insulating dielectric is deposited overlying the nanotips, and an electrically conductive top electrode is deposited overlying dielectric-covered nanotips. Typically, the dielectric is deposited by forming a thin layer of dielectric overlying the nanotips using an atomic layer deposition (ALD) process. In one aspect, the electrically insulating dielectric covering the nanotips forms a three-dimensional interface of dielectric-covered nanotips. Then, the electrically conductive top electrode overlying the dielectric-covered nanotips forms a three-dimensional top electrode interface, matching the first three-dimensional interface of the dielectric-covered nanotips.