The low toxicity of Se nanoparticles (NPs) makes it a suitable candidate for biomedical and sensing applications. Herein, we, for the first time, report the modification of a pencil graphite electrode with Se nanostructures (Se/PGE) by a facile chemical bath deposition (CBD) method. Hydrazine, a routine chemical in various industries, is toxic even in trace amounts and poses a serious threat due to its carcinogenic and mutagenic nature. Therefore, it is crucial to detect its presence in aqueous media. The Se/PGE exhibited outstanding, reproducible, and selective electrocatalytic activity for hydrazine determination. The Se/PGE displayed a stable amperometric response with a wide linear concentration range of 1 μM–50 mM, a LOQ of 90 nM, a very low LOD of 45 nM, and a sensitivity of 0.813 μA·μM–1·cm–2. Moreover, Se/PGE showed a negligible response toward common interferences like NO3–1, CH3COO–1, phenol, and DMF at the selected applied potential. Applying the as-fabricated sensor for hydrazine detection in real-life samples (drinking water) showed satisfactory results with a recovery percentage of 96.9%. Further, our methodology paves the way to fabricate modified pencil graphite electrodes (PGEs) through a convenient CBD method.