Polycrystalline zinc selenide (p-ZnSe) is one of the most widely used infrared optical materials. Since p-ZnSe possesses soft and brittle properties, it is machined at micro/nanoscale for achieving ductile mode machining. In micro/nanoscale machining, the tool shape and edge sharpness have significant influence on tool-workpiece contact and mechanism of chip formation, and consequently affect the machined surface integrity. To reveal the effect of tool shape on the machined surface integrity of p-ZnSe, in this study, round-nose and spherical diamond tools, which have different tool geometries and edge radii, were used for machining p-ZnSe. Results present that the tool nose radius and edge radius are critical factors for the chip formation and phase transformation of the workpiece material. Increasing the edge radius or using spherical tool causes a burnishing effect without material removal. Local plastic deformation is caused by an intense compressive stress under a high effective negative rake angle. In addition, results show that no matter what kind of tool is used and how the material is deformed, grain boundary has a great influence on the machined surface integrity. This study provides an insight into the deformation mechanism of polycrystalline brittle material in nanoscale machining with respect to different tool shapes, which will guide improvement of machined surface integrity.