Formation of the triangular skyrmion-lattice is found in a tetragonal polar magnet VOSe$_2$O$_5$. By magnetization and small-angle neutron scattering measurements on the single crystals, we identify a cycloidal spin state at zero field and a Neel-type skyrmion-lattice phase under a magnetic field along the polar axis. Adjacent to this phase, another magnetic phase of an incommensurate spin texture is identified at lower temperatures, tentatively assigned to a square skyrmion-lattice phase. These findings exemplify the versatile features of Neel-type skyrmions in bulk materials, and provide a unique occasion to explore the physics of topological spin textures in polar magnets.