Although Paolo Veronese's beginnings as a painter are normally placed around 1548, there is every reason to retrodate his earliest works to about 1543 when he emerged from the studio of Antonio Badile. This study reexamines these pictures, returning several portraits to him that have not been considered in the recent literature including the unusual Collatino Collalto. The frescoes in Palazzo Canossa in Verona belong with his earliest efforts in this medium, and the Mystic Marriage of Saint Catherine (New Haven, Yale University Art Gallery), and the Conversion of the Magdalene (London, National Gallery) find their correct context in the years around 1547. This, in addition, allows a clearer understanding of Battista Zelotti's position as Paolo's early imitator.