Vrtojba was first mentioned in the early 13th century as Toyfa, Toyua, or Tojva in a list of properties belonging to the Counts of Gorizia. Its etymology is unknown, but is likely of pre-Slavic origin. By 1350 it was listed as Vertoib. The population increased in the 16th and 17th centuries with settlers from areas further south affected by Ottoman raids moving to the fertile countryside around Gorizia. In the late 18th and early 19th centuries, Vrtojba became known for its early season vegetables and potatoes with regular supply to the markets of Gorizia and beyond. Although this fame still continues to some extent today, industrialization of Nova Gorica after the Second World War meant workers also settled in the village and the urban expansion in recent decades has virtually turned Vrtojba into the southern suburbs of Nova Gorica.