The settlement of Nea Nikomedeia is situated 11 kilometres approximately to the northeast of Veroia. The excavations of the 1960s brought to light a large part of the settlement, whose size is estimated to be 2,400 square metres. It is one of the most extensive and better investigated settlements of the Early Neolithic in Greece. Sporadic architectural remains have confirmed the use of this area during the Late Neolithic as well.

The two architectural phases of the Early Neolithic provide important information concerning the settlement organization of the farming and stock-raising community. The earlier phase consisted of square timber-post framed dwellings, built free-standing. Their sides were approximately 8 metres long and consisted of lean tree trunks, placed vertically and at a distance of 0,9-1,2 metres. In between them thin branches and reeds were placed, formimg the hut walls, which were then covered from the inside and the outside with quantities of hay and clay. Posts in the interior of these buildings supported the hipped roof, consisting of branches, reeds, clay and hay.

Square dwellings were arranged around a larger one (12X12 metres), which was initially interpreted to be a shrine because of its dimensions and the objects found in it (12 figurines, adzes etc.). During the late phase of the Early Neolithic, rectangular timber-post framed dwellings were constructed as well, in which a wide and a narrow space is discernible.

Pottery typical of the Early Neolithic, flint blades, stone adzes, clay figurines with cruciform eyes and beak-shaped noses, seals for the adornment of the body, a frog-shaped pendant from steatite as well as clay spindle whorls for spinning wool and bone tools, reveal the activities of the Neolithic inhabitants of the plain of Veroia.