Gas-fueled power plants are considerably effective in power system operation during peak hours due to their high up and down ramping rates. By increasing the penetration of gas-fueled power plants in power systems and development of new technologies, such as power-to-gas (ptg) units, coordinated scheduling of both electricity and natural gas (NG) networks has attracted systems researchers’ attention. The NG volume generated by ptg units are stored in storages to directly supply the NG demands, or to sell in NG markets. If necessary, the stored NG volumes are reconverted into electricity which may be a suitable replacement for batteries and storages in electricity network in long term. In this paper, a mixed integer linear programming (MILP) model is proposed for stochastic coordinated scheduling of electricity and NG networks with ptg units, considering uncertainties of charging and discharging available capacities of vehicle to grid (v2g) stations. A test network integrating modified 24-bus IEEE electricity network and Belgium gas network including nine power stations (three of them are gas-fueled), three v2g stations, and three ptg stations is studied to evaluate the effectiveness of the proposed model. Simulation results demonstrate the effectiveness of ptg units in handling the uncertainties of v2g stations charging and discharging. Besides, the effectiveness of coordinated scheduling of both electricity and NG networks in comparison with independent scheduling of both networks is demonstrated.