The earliest mediæval heraldry? – the Notitia Dignitatum
The Notitia Dignitatum has some fascinating proto-heraldry (late 4-early 5C CE) in the form of military shield designs, with different units having their own devices. There's a great website on it here. I discovered it via the Osprey books on the late Roman and Romano-Byzantine armies. It's interesting to see the roots of armorial devices in the very early Middle Ages. I recommend downloading the Paris and Munich editions!