What type of authentication is the remote service expecting? (Basic, Negotiate, NTLM, OAuth, other…), When you set up your Postman request what are you using?
I recently interacted with a semi-REST API, that is expecting to Negotiate or NTLM, but would reject Basic.
I ended up adding the credentials (Add Credential) to the Windows Credential Manager and leaving the authentication properties for the HTTP Request activity unset.