1585, from newfound + land (n.). In reference to a type of dog, from 1773. Related: Newfoundlander. Colloquial shortening Newfie for the inhabitants or the place is recorded from 1942.
newborn
newcomer
newel
newfangled
newfound
Newfoundland
Newgate
newish
newly
newlywed
new-made