The N-degron pathway regulates protein stability based on the identity of the N-terminal amino acid. Ubiquitin E3 ligase (E3) modules (known as N-recognins) in the N-degron pathway direct ubiquitin to substrate proteins. We have uncovered and structurally characterised an unusual E3 ligase module within a known N-recognin (UBR4). We show that this 400-residue single subunit E3 module recruits Ube2A in vivo and present a structure of the UBR4-Ube2A complex. Together our structural and in vitro activity data provide mechanistic insight into UBR4 function and Ube2A recruitment. Our data suggest that evolutionarily conserved domains with E3 ligase activity have eluded sequence-based predictions and that activity-based profiling is likely to uncover novel E3s.