As historians have rightly suggested, the religious freedom granted by the Edict of Milan in 313 allowed for a fundamental change in status for Christianity. Inasmuch as the Church was no longer regarded an illegal ‘sect’, Christianity became free to expand its influence within the Empire, gradually supplanting paganism and becoming the customary religion. Towards the end of the fourth century – during the reign of Theodosius – the Edict of Thessalonica in 380 and the Council of Constantinople in 382 imposed Nicene Christianity as the ‘state religion’. These events led to a major change in perspective. After this time, the spiritual superiority of Christianity over paganism and the suppression of pagan traditions are key elements in our understanding of Christian historiography. Drawing clear lines of demarcation between orthodoxy and heterodoxy almost immediately became a necessary condition to neutralise both manifestations of religious dissidence and expressions of diversity. This paper will examine two fundamental parameters that were commonly regarded as indicators of orthodoxy: coherence of behaviour and knowledge of doctrine. These concepts only emerged gradually though, and were adapted to the historical circumstances from time to time. Norms and decrees issued by the ecclesiastical hierarchy and constitutions promulgated by emperors are important sources from which to detect and analyse provisions directed against heretics and pagans. The examination of the situation in Hispania, most notably during the last decades of the fourth century, provides an interesting picture of both this cultural transition and the conflicts it caused.