The name derives from the Greek verb παραμένω, meaning "to stand near something". Unlike other major guard units in the Palaiologan army like the Varangian Guard, the regiment of the Paramonai was a native Byzantine formation, although little else is known about it. Its existence is safely attested in the literary sources only for the period from 1272 until 1315.
They are still mentioned by the mid-14th century writer Pseudo-Kodinos, however, who records that the regiment had two divisions, one on foot and the other on horse, each commanded by an allagator, and that all the soldiers were armed with swords. The veracity of Kodinos's account is impossible to ascertain.