Is MS Project 2016 compatible with Office 365?

That's correct, it's a https://support.office.com/en-gb/article/Office-installed-with-Click-to-Run-and-Windows-Installer-on-same-computer-isn-t-supported-30775ef4-fa77-4f47-98fb-c5826a6926cd assuming it's an error similar to below (the wording may be different):

Those Office 365 and MS Project 2016 installations you mentioned use two different technologies and can't coexist.

"Click-to-Run is the technology used to install Office 365 subscription and most other Office 2013 and Office 2016 products. Windows Installer technology (MSI) is used to install the volume license editions of Office, like Microsoft Office Professional Plus and Microsoft Office Standard."

"Unfortunately, you can't have Office products of the same version (like 2013 or 2016) that use two different installation technologies installed on the same computer. This also applies to standalone applications like Access, Visio, Project, Skype for Business, or OneDrive for Business."

Here are more specifics on what is supported as well as what isn't: https://technet.microsoft.com/en-us/library/mt712177%28v=office.16%29.aspx?f=255&MSPPError=-2147217396.

Your options are somewhat limited, if you have access to Project 2013, I believe that will install ok.  If you had a volume licence version of Project 2016, there is a way to have Project 2016 and Office 365 but it takes some setting up as outlined here -  https://docs.microsoft.com/en-gb/DeployOffice/use-the-office-deployment-tool-to-install-volume-licensed-editions-of-visio-2016.