This paper reports capture and detection of pathogenic bacteria based on AC dielectrophoresis (DEP) and electrochemical impedance spectroscopy (EIS) employing an embedded vertically aligned carbon nanofiber (VACNF) nanoelectrode array (NEA) versus a macroscopic indium-tin-oxide (ITO) transparent electrode in "points-and-lid'' configuration. The nano-DEP device was fabricated using photolithography processes to define an exposed active region on a randomly distributed NEA and a microfluidic channel on ITO to guide the flow of labeled Escherichia coli cells, respectively, and then bond them into a fluidic chip. A high-frequency (100 kHz) AC field was applied to generate positive DEP at the tips of exposed CNFs. Enhanced electric field gradient was achieved due to reduction in electrode size down to nanometer scale which helped to overcome the large hydrodynamic drag force experienced by E. coli cells at high flow velocities (up to 1.6 mm/s). This DEP device was able to effectively capture a significant number of E. coli cells. Significant decrease in the absolute impedance at the NEA was observed in EIS experiments. The results obtained in this study suggest the possibility of integration of a fully functional electronic device for rapid, reversible and label-free capture and detection of pathogenic bacteria.