Begin by adding a new contact. Once on the contact form, scroll down to department. Select Add Department:

Name the department and select confirm.

Begin by going to the contacts page. Select the contact you wish to edit and click the 3 dots to the right of the contact information:

From the dropdown, select the department you wish to move the contact to.