To remove nitrate from wastewater, a novel bioelectrochemical denitrification system is introduced. In this proposed system, biological reactions are coupled with reactions on the electrode, whereby the electrons are transferred to the bacterial enzymes via a mediator as an electron carrier. The denitrification reaction was achieved with permeabilized Ochrobactrum anthropi SY509 containing denitrifying enzymes, such as nitrate reductase, nitrite reductase, and nitrous oxide reductase, and methyl viologen was used as the mediator. The electron transfer from the electrode to the enzymes in the bacterial cells was confirmed using cyclic voltammetry. A high removal efficiency of nitrate was achieved when the bioelectrochemical system was used with the permeabilized cells. Furthermore, when the permeabilized cells were immobilized to a graphite felt electrode using a calcium alginate matrix containing graphite powder, a high removal efficiency was achieved (4.38 nmol/min mg cell) that was comparable to the result when using the free permeabilized cells.