Toluene is extensively used in many industrial products, which needs to be effectively detected by sensitive gas sensors even at low-ppm-level concentrations. Here, NiFeO nano-octahedrons were calcinated from NiFe-bimetallic metal-organic framework (MOFs) octahedrons synthesized by a facile refluxing method. The co-existence of p-Phthalic acid (PTA) and 3,3-diaminobenzidine (DAB) promotes the formation of smooth NiFe-bimetallic MOFs octahedrons. After subsequent thermal treatment, a big weight loss (about 85%) transformed NiFeO nanoparticles (30 nm) into NiFeO porous nano-octahedrons with hollow interiors. The NiFeO nano-octahedron based sensor exhibited excellent gas sensing properties for toluene with a nice stability, fast response, and recovery time (25 s/40 s to 100 ppm toluene), and a lower detection limitation (1 ppm) at 260 °C. The excellent toluene-sensing properties can not only be derived from the hollow interiors combined with porous nano-octahedrons to favor the diffusion of gas molecules, but also from the efficient catalytic activity of NiFeO nanoparticles.