I'm not sure what unconstitutional means here. The department is not named in the constitution, but then neither were the overwhelming majority of such. (You could say, "that ship has sailed" once the Department of the Navy was created.) It embraces quite a few agencies that go way back, including the Coast Guard, and the customs component of ICE.