The mkdir() call has been around since BSD 4.2. It was later added to SYSV 3.0. See: http://pubs.opengroup.org/onlinepubs/9699919799/functions/mkdir.html
BSD 4.2 came out in 1984: http://www.unix.org/what_is_unix/history_timeline.html
If access to a kernel mode entry point in UNIX via a syscall is permitted from user mode without restriction, what duskwuff indicates, then setuid is not required.