The city of Melbourne in southeast Australia experiences frequent heatwaves and their frequency, intensity and duration are expected to increase in the future. In addition, Melbourne is the fastest growing city in Australia and experiencing rapid urban expansion. Heatwaves and urbanization contribute in intensifying the Urban Heat Island (UHI) effect, i.e., higher temperatures in urban areas as compared to surrounding rural areas. The combined effects of UHI and heatwaves have substantial impacts on the urban environment, meteorology and human health, and there is, therefore, a pressing need to investigate the effectiveness of different mitigation options. This study evaluates the effectiveness of urban vegetation patches such as mixed forest (MF), combination of mixed forest and grasslands (MFAG), and combination of mixed shrublands and grasslands (MSAG) in reducing UHI effects in the city of Melbourne during one of the most severe heatwave events. Simulations are carried out by using the Weather Research and Forecasting (WRF) model coupled with the Single Layer Urban Canopy Model (SLUCM). The fractions of vegetated patches per grid cell are increased by 20%, 30%, 40% and 50% using the mosaic method of the WRF model. Results show that by increasing fractions from 20 to 50%, MF reduces near surface (2 m) UHI (UHI2) by 0.6–3.4 °C, MSAG by 0.4–3.0 °C, and MFAG by 0.6–3.7 °C during the night, but there was no cooling effect for near surface temperature during the hottest part of the day. The night-time cooling was driven by a reduction in storage heat. Vegetated patches partitioned more net radiation into latent heat flux via evapotranspiration, with little to no change in sensible heat flux, but rather, a reduction in the storage heat flux during the day. Since the UHI is driven by the release of stored heat during the night, the reduced storage heat flux results in reductions in the UHI. The reductions of the UHI2 varied non-linearly with the increasing vegetated fractions, with lager fractions of up to 50% resulting in substantially larger reductions. MF and MFAG were more effective in reducing UHI2 as compared to MSAG. Vegetated patches were not effective in improving HTC during the day, but a substantial improvement of HTC was obtained between the evening and early morning particularly at 2100 local time, when the thermal stress changes from strong to moderate. Although limited to a single heatwave event and city, this study highlights the maximum potential benefits of using vegetated patches in mitigating the UHI during heatwaves and the overall principles are applicable elsewhere.